Independent Spanning Trees on Multidimensional Torus Networks

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