Parallel construction of optimal independent spanning trees on hypercubes

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Tang et al. [S.-M. Tang, Y.-L. Waug, Y.-H. Leu. Optimal independent spanning trees on hypercubes, Journal of Information Science and Engineering 20 (2004) 143-155] studied the problem of constructing k ISTs on k-dimensional hypercube Q(k), and provided a recursive algorithm for their construction (i.e., for constructing k ISTs of Q(k), it needs to build k - 1 ISTs of Q(k-1) in advance). This kind of construction forbids the possibility that the algorithm could be parallelized. In this paper, based on a simple concept called Hamming distance Latin square. we design a new algorithm for generating k ISTs of Q(k). The newly proposed algorithm relies on a simple rule and is easy to be parallelized. As a result. we show that the ISTs we constructed are optimal in the sense that both the heights and the average path length of trees are minimized. (c) 2006 Elsevier B.V. All rights reserved.