Multicasting in the Hypercube, Chord and Binomial Graphs

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.