Vertex-independent spanning trees in complete Josephus cubes

• Published in: Theoretical computer science 2025-02, Vol.1025, p.114969, Article 114969
• Main Authors: He, Qi, Wang, Yan, Fan, Jianxi, Cheng, Baolei
• Format: Article
• Language: English
• Subjects: Complete Josephus cubes; Josephus cubes; Parallel algorithm; Vertex-independent spanning trees
• ISSN: 0304-3975
• DOI: 10.1016/j.tcs.2024.114969

Vertex-independent spanning trees (short for VISTs) serve as pivotal constructs in numerous network algorithms and have been the subject of extensive research for three decades. The n-dimensional complete Josephus cube CJCn, derived from the Josephus cube, was first proposed to achieve better fault tolerance while maximizing routing efficiency (no sacrificing routing efficiency). Compared to the Josephus cube, it exhibits enhanced symmetry, improved connectivity, and better fault tolerance while maintaining efficient embedding, incremental scalability, and short diameter (⌈n2⌉). This paper studies the existence and construction of n+2 VISTs in CJCn rooted at an arbitrary vertex. To determine the specific connection edge between vertex v and its parent in the spanning tree Ti, three algorithms were first proposed to calculate the values of Fv,i, Mv,i, and Hv,i, respectively, where v∈V(CJCn) and i∈{0,1,⋯,n+1}. Based on these algorithms, a parallel algorithm is proposed to construct n+2 (n≥4) VISTs in CJCn using 2n processors. As CJCn is (n+2)-connected, our algorithm is designed to yield the optimal number of resulting VISTs for n≥4. Finally, we present the theoretical proof of the parallel algorithm and demonstrate that its time complexity is O(n).