Previous [1] [2] [3] [4] [5] [6] [7] 8

Journal of Inforamtion Science and Engineering, Vol.7 No.4, pp.613-633 (December 1991)
Hierarchical Spanning Trees in Incomplete
Hypercubes

Jenn-Yang Tien and Wei-Pang Yang+
Institute of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan, R.O.C.
+Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan, R.O.C.

Incomplete hypercubes, comprised of an n-cube and a k-cube, are gaining increasing attention as a possible solution for the limited scalability of hypercubes. In this paper, two types of spanning trees in incomplete hypercubes, the binomial hierarchical spanning tree and the balanced hierarchical spanning tree, are proposed and applied to two frequently used communication operations: broadcasting and distributing. The distributing operation is similar to the broadcasting operation, but messages destined for different nodes are distinct. Based on the binomial hierarchical spanning tree, the broadcasting algorithm is optimal. Based on the balanced hierarchical spanning tree, the one-port distributing algorithm uses communication bandwidth effectively and attains a speedup of k/2 or n/2 over the algorithm based on the binomial hierarchical spanning tree, depending on whether the source node is in the front (n-)cube or the back (k-)cube.

Keywords: balanced hierarchical spanning tree, binomial hierarchical spanning tree, broadcasting, distributing, incomplete hypercube

Received June 16, 1991; revised November 1, 1991.
Communicated by Wen-Tsuen Chen.