Abstract
Multicasting in the Hypercube, Chord and Binomial Graphs
by: Christopher C. Cipriano and Teofilo F. Gonzalez
Abstract:
We discuss multicasting for the n-cube network and its close variants, the Chord and the Binomial Graph (BNG) Network. We present simple transformations and proofs that establish that the sp-multicast (shortest path) and Steiner tree problems for the n-cube, Chord and the BNG network are NP-Complete.
Keywords:
NP-Completeness, n-cube, binomial graphs, Chord, multicasting, Steiner trees.
Date:
June 2009
Document: 2009-09
