Transparent Gif

Department of Computer Science

University of California, Santa Barbara

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

XHTML Validation | CSS Validation
Updated 14-Nov-2005
Questions should be directed to: webmaster@cs.ucsb.edu