Two algorithms for constructing independent spanning trees in (n,k)-star graphs

Jie Fu Huang, Eddie Cheng, Sun Yuan Hsieh

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)


In a graph G, two spanning trees T1 and T2 are rooted at the same vertex r. If, for every v ∈ V(G), the paths from v to the root r in T1 and T2 are internally vertex-disjoint, they are called independent spanning trees (ISTs). ISTs can be applied in numerous fields, such as fault-tolerant broadcasting and secure message distribution. The (n,k)-star graphs Sn,k constitute a generalized version of the star network. The method of constructing ISTs in (n,k)-star graphs remains unknown. In this paper, we propose one recursive algorithm and one parallel algorithm for constructing ISTs on (n,k)-star graphs. The main ideas of the recursive algorithm are to use induction to change small trees into large trees, to use a modified breadth-first search (MBFS) traversal to create a frame for an IST, and to use a breadth-first search (BFS) traversal to connect the rest of nodes. The main ideas of the parallel algorithm are to create frames through MBFS traversals in parallel, and to use some specific rules to connect the rest of nodes in parallel. We also present validation proofs for both algorithms, and analyze the time complexities of both algorithms. The time complexity of the recursive algorithm in Sn,k is O(n × (nn!k)! ), where (nn!k)! is the number of nodes of Sn,k. The time complexity of the parallel algorithm can be reduced to O((nn!k)! ) if the system has n − 1 processors computing in parallel. Both algorithms are correct with the stated time complexity values; the parallel algorithm is more efficient than the recursive algorithm.

頁(從 - 到)175932-195947
期刊IEEE Access
出版狀態Published - 2020

All Science Journal Classification (ASJC) codes

  • 電腦科學(全部)
  • 材料科學(全部)
  • 工程 (全部)


深入研究「Two algorithms for constructing independent spanning trees in (n,k)-star graphs」主題。共同形成了獨特的指紋。