Recursive and parallel constructions of independent spanning trees in alternating group networks. Issue 4 (1st October 2020)

• Record Type: Journal Article
• Authors: Huang, Jie-Fu; Hsieh, Sun-Yuan
• Is Part Of: International journal of computer mathematics. Volume 5:Issue 4(2020)
• Page Start: 234
• Page End: 262
• Publication Date: 2020-10-01
• Subjects: Independent spanning trees -- alternating group networks -- Cayley graph -- recursive algorithm -- parallel algorithm; 05C05 -- 68R10; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1814418
• Languages: English
• ISSNs: 2379-9927

Abstract

Abstract : 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.)