Broadcasting on incomplete hypercubes

Incomplete hypercubes make the hypercubes more flexible on task allocation in large cubes, cost of manufacturing hardware, and hypercubes with faulty nodes. The authors devise and analyze broadcasting algorithms based on the hierarchical binomial spanning trees, hierarchical edge-disjoint spanning trees and edge-disjoint spanning trees in an incomplete hypercube of 2n+2k nodes, where 0<or=k<n. The hierarchical binomial spanning trees have the shortcoming of unbalanced load on parallel paths. In the one-port communication model, in which each node can send message along only one link at a time, the hierarchical edge-disjoint spanning tree algorithms are optimal within a factor of two. The edge-disjoint spanning trees algorithms are optimal with a factor of n+1/k+1 For all-port communication, in which a node can send messages to any number of links adjacent to it, the edge-disjoint spanning trees algorithms are strictly optimal.