Previous [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]

@

Journal of Information Science and Engineering, Vol. 20 No. 1, pp. 143-156 (January 2004)

Optimal Independent Spanning Trees on Hypercubes*

Shyue-Ming Tang, Yue-Li Wang+ and Yung-Ho Leu+
Fu Hsing Kang College
Taipei, 112 Taiwan
+Department of Information Management
National Taiwan University of Science and Technology
Taipei, 106 Taiwan

Two spanning trees rooted at some vertex r in a graph G are said to be independent if for each vertex v of G, v ¹ r, the paths from r to v in two trees are vertex-disjoint. A set of spanning trees of G is said to be independent if they are pairwise independent. A set of independent spanning trees is optimal if the average path length of the trees is the minimum. Any k-dimensional hypercube has k independent spanning trees rooted at an arbitrary vertex. In this paper, an O(kn) time algorithm is proposed to construct k optimal independent spanning trees on a k-dimensional hypercube, where n = 2k is the number of vertices in a hypercube.

Keywords:  independent spanning trees, internally disjoint paths, hypercubes, fault-tolerant broadcasting, recursive algorithm

@

Full Text () Retrieve PDF document (200401_08.pdf)

Received January 31, 2003; accepted July 4, 2003.
Communicated by Shiuh-Pyng Shieh.
* A preliminary version of this paper was presented at the 2002 International Computer Symposium, 2002.