Recursive and parallel constructions of independent spanning trees in alternating group networks

Jie Fu Huang, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish
Pages (from-to)234-262
Number of pages29
JournalInternational Journal of Computer Mathematics: Computer Systems Theory
Volume5
Issue number4
DOIs
Publication statusPublished - 2020 Oct 1

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Recursive and parallel constructions of independent spanning trees in alternating group networks'. Together they form a unique fingerprint.

Cite this