Parallel construction of edge-independent spanning trees in complete Josephus cubes

The n-dimensional complete Josephus cube \(CJC_n\) $CJ{C}_n$ is the edge-augmented Josephus cube suitable for massively parallel processing systems. Compared with the Josephus cube, \(CJC_n\) $CJ{C}_n$ has better fault tolerance performance while maintaining high scalability. A set of k ( \(k\ge 2\) $k\ge 2$ ) spanning trees rooted at the same vertex r in graph G is called edge-independent trees (EISTs for short) when the k paths from \(v\in V(G)\setminus \{r\}\) $v\in V(G)\backslash \{r\}$ to r have no common edges. EISTs are crucial in distributing information, ensuring fault-tolerant broadcasting, reliable data transmission, and IP fast rerouting. This paper studies the existence and construction of \(n+2\) $n+2$ EISTs rooted at an arbitrary vertex in \(CJC_n\) $CJ{C}_n$ . We present a parallel Algorithm CJC_EIST for constructing \(n+2\) $n+2$ EISTs, enabling each vertex to determine its parent in each spanning tree instantaneously. Using \(2^n\) $2^n$ processors ( \(|V(CJC_n)=2^n|\) $|V(CJ{C}_n)=2^n|$ ), our algorithm achieves parallel execution with O(n) time complexity. As \(CJC_n\) $CJ{C}_n$ is \((n+2)\) $(n+2)$ -edge-connected, the number of resulting EISTs constructed by Algorithm CJC_EIST is optimal. Finally, we provide the corresponding theoretical proof of the algorithm and perform simulation experiments using the resulting spanning trees.