Back to Search
Start Over
Parallel construction of optimal independent spanning trees on hypercubes
- Source :
-
Parallel Computing . Feb2007, Vol. 33 Issue 1, p73-79. 7p. - Publication Year :
- 2007
-
Abstract
- 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. [Copyright &y& Elsevier]
- Subjects :
- *SPANNING trees
*TREE graphs
*GRAPHIC methods
*BANDWIDTHS
*HYPERCUBES
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 01678191
- Volume :
- 33
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Parallel Computing
- Publication Type :
- Academic Journal
- Accession number :
- 24138305
- Full Text :
- https://doi.org/10.1016/j.parco.2006.12.001