TY - JOUR
T1 - Recursive and parallel constructions of independent spanning trees in alternating group networks
AU - Huang, Jie Fu
AU - Hsieh, Sun Yuan
N1 - Publisher Copyright:
© 2020 Informa UK Limited, trading as Taylor & Francis Group.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/10/1
Y1 - 2020/10/1
N2 - In this paper, we propose a recursive algorithm and a parallel algorithm for constructing independent spanning trees in ANn. The main ideas of the recursive algorithm are to construct large trees from small trees, use triangle breadth-first search (TBFS) to build a frame of an IST, and use breadth-first search (BFS) to link the rest of the nodes. The main ideas of the parallel algorithm are to build frames through TBFS in parallel, and to use the specific rules to link the rest of the nodes in parallel. We prove the correctness of both algorithms for constructing ISTs in AN n. Both algorithms are accurate; furthermore, the parallel algorithm is more ecient than the recursive algorithm. (An extended abstract of this paper appeared in: Jie-Fu Huang and Sun-Yuan Hsieh ‘Two methods for constructing independent spanning trees in alternating group networks’ Proceedings of International Conference on Creative Lifestyle Computing (ICCLC), 2020.).
AB - In this paper, we propose a recursive algorithm and a parallel algorithm for constructing independent spanning trees in ANn. The main ideas of the recursive algorithm are to construct large trees from small trees, use triangle breadth-first search (TBFS) to build a frame of an IST, and use breadth-first search (BFS) to link the rest of the nodes. The main ideas of the parallel algorithm are to build frames through TBFS in parallel, and to use the specific rules to link the rest of the nodes in parallel. We prove the correctness of both algorithms for constructing ISTs in AN n. Both algorithms are accurate; furthermore, the parallel algorithm is more ecient than the recursive algorithm. (An extended abstract of this paper appeared in: Jie-Fu Huang and Sun-Yuan Hsieh ‘Two methods for constructing independent spanning trees in alternating group networks’ Proceedings of International Conference on Creative Lifestyle Computing (ICCLC), 2020.).
UR - http://www.scopus.com/inward/record.url?scp=85090577330&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090577330&partnerID=8YFLogxK
U2 - 10.1080/23799927.2020.1814418
DO - 10.1080/23799927.2020.1814418
M3 - Article
AN - SCOPUS:85090577330
VL - 5
SP - 234
EP - 262
JO - International Journal of Computer Mathematics: Computer Systems Theory
JF - International Journal of Computer Mathematics: Computer Systems Theory
SN - 2379-9927
IS - 4
ER -