TY - GEN
T1 - A Parallel Algorithm for Constructing Multiple Independent Spanning Trees in Bubble-Sort Networks
AU - Kao, Shih Shun
AU - Klasing, Ralf
AU - Hung, Ling Ju
AU - Hsieh, Sun Yuan
N1 - Funding Information:
This research was supported by the LaBRI under the “Projets émergents” program. This study has been carried out in the frame of the “Investments for the future” Programme IdEx Bordeaux - SysNum (ANR-10-IDEX-03-02).
Funding Information:
This research was supported by the LaBRI under the ?Projets ?mergents? program. This study has been carried out in the frame of the ?Investments for the future? Programme IdEx Bordeaux-SysNum (ANR-10-IDEX-03-02).
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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 secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. [Journal of Combinatorial Optimization 38 (2019) 972–986] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks Bn and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O(n· n! ) of our algorithm is asymptotically optimal, where n is the dimension of Bn and n! is the number of vertices of the network.
AB - 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 secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. [Journal of Combinatorial Optimization 38 (2019) 972–986] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks Bn and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O(n· n! ) of our algorithm is asymptotically optimal, where n is the dimension of Bn and n! is the number of vertices of the network.
UR - http://www.scopus.com/inward/record.url?scp=85122000250&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85122000250&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-93176-6_22
DO - 10.1007/978-3-030-93176-6_22
M3 - Conference contribution
AN - SCOPUS:85122000250
SN - 9783030931759
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 252
EP - 264
BT - Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings
A2 - Wu, Weili
A2 - Du, Hongwei
PB - Springer Science and Business Media Deutschland GmbH
T2 - 15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021
Y2 - 20 December 2021 through 22 December 2021
ER -