| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427554 | Information Processing Letters | 2010 | 4 Pages |
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, even when every destination vertex is at a distance two from the source vertex.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
