Multicasting in the Hypercube, Chord and Binomial Graphs

Report ID: 
2009-09
Authors: 
Christopher C. Cipriano and Teofilo F. Gonzalez
Date: 
2009-06-01 05:00:00

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.

Document

PDF icon 2009-09.pdf