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.
| Previous | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | [ 5 ] | [ 6 ] | [ 7 ] | [ 8 ] | [ 9 ] | [ 10 ] | [ 11 ] |
¡@
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
¡@
Received January 31, 2003; accepted July 4, 2003.
Retrieve
PDF document (200401_08.pdf)
Communicated by Shiuh-Pyng Shieh.
* A preliminary version of
this paper was presented at the 2002 International Computer Symposium, 2002.