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. Wang, 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.