Parallel construction of optimal independent spanning trees on hypercubes

✍ Scribed by Jinn-Shyong Yang; Shyue-Ming Tang; Jou-Ming Chang; Yue-Li Wang

• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 212 KB
• Volume: 33
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/j.parco.2006.12.001

✦ Synopsis

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.