1. Independent Spanning Trees on Multidimensional Torus Networks.
- Author
-
Shyue-Ming Tang, Jinn-Shyong Yang, Yue-Li Wang, and Jou-Ming Chang
- Subjects
SPANNING trees ,COMPUTER networks ,BROADCASTING industry ,FAULT-tolerant computing ,PARALLEL algorithms - Abstract
Two spanning trees rooted at vertex r in a graph G are called independent spanning trees (ISTs) if for each vertex v in G, v ≠ r, the paths from vertex v to vertex r in these two trees are internally distinct. If the connectivity of G is k, the IST problem is to construct k ISTs rooted at each vertex. The IST problem has found applications in fault-tolerant broadcasting, but it is still open for general graphs with connectivity greater than four. In this paper, we shall propose a very simple algorithm for solving the IST problem on multidimensional torus networks. In our algorithm, every vertex can determine its parent for a specific independent spanning tree only depending on its own label. Thus, our algorithm can also be implemented in parallel systems or distributed systems very easily. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF