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

¡@

**Shyue-Ming Tang, Yue-Li Wang ^{+} and Yung-Ho Leu^{+} **

Taipei, 112 Taiwan

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* = 2^{k} is the number of vertices in a hypercube.

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

¡@

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.