TY - GEN
T1 - Constructing Independent Spanning Trees in Alternating Group Networks
AU - Huang, Jie Fu
AU - Hsieh, Sun Yuan
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - In a graph G, two spanning trees and are rooted at the same vertex r. If for every the paths from v to the root r in and are internally vertex-disjoint, they are independent spanning trees (ISTs). ISTs have numerous applications, such as secure message distribution and fault-tolerant broadcasting. The alternating group network (n stands for the dimension) is a subclass of Cayley graphs, and the approach of constructing ISTs in has not been proposed until now. In this paper, we propose a recursive algorithm for constructing ISTs in. The algorithm is a top-down approach, and the parent of one node in an IST is not determined by any rule. The correctness of the algorithm is verified, and the time complexity is analyzed. We use PHP to implement the algorithm and test cases from. The testing results show that all trees are ISTs in all cases. We conclude that our algorithm is not only correct but also efficient.
AB - In a graph G, two spanning trees and are rooted at the same vertex r. If for every the paths from v to the root r in and are internally vertex-disjoint, they are independent spanning trees (ISTs). ISTs have numerous applications, such as secure message distribution and fault-tolerant broadcasting. The alternating group network (n stands for the dimension) is a subclass of Cayley graphs, and the approach of constructing ISTs in has not been proposed until now. In this paper, we propose a recursive algorithm for constructing ISTs in. The algorithm is a top-down approach, and the parent of one node in an IST is not determined by any rule. The correctness of the algorithm is verified, and the time complexity is analyzed. We use PHP to implement the algorithm and test cases from. The testing results show that all trees are ISTs in all cases. We conclude that our algorithm is not only correct but also efficient.
UR - http://www.scopus.com/inward/record.url?scp=85091076398&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85091076398&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-58150-3_16
DO - 10.1007/978-3-030-58150-3_16
M3 - Conference contribution
AN - SCOPUS:85091076398
SN - 9783030581497
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 198
EP - 209
BT - Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings
A2 - Kim, Donghyun
A2 - Uma, R.N.
A2 - Cai, Zhipeng
A2 - Lee, Dong Hoon
PB - Springer Science and Business Media Deutschland GmbH
T2 - 26th International Conference on Computing and Combinatorics, COCOON 2020
Y2 - 29 August 2020 through 31 August 2020
ER -