About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
Broadcasting on incomplete hypercubes
Abstract
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.