A Parallel Algorithm to Construct Node-Independent Spanning Trees on the Line Graph of Locally Twisted Cube
Zhiyong Pan, Baolei Cheng, Jianxi Fan, Huanwen Zhang · 2021
An interconnection network can be abstracted into a graph, and the basic mathematical research in the graph can provide a good reference for the research in the practical application. The study of node-independent spanning trees (node-ISTs) in a graph has received extensive attention because of their application in reliable communication, fault-tolerant broadcasting and secure message distribution, and has achieved remarkable results on many special networks. But there are few results in the line graph of them. As one of the typical variations of hypercube, locally twisted cube has many excellent properties, whose line graph has all the advantages of locally twisted cube. So it makes sense to do some research on the line graph of locally twisted cube. In this paper, we propose a parallel algorithm to construct$2n-2$node-ISTs rooted at node$[u,\ N(u, 2)]$, where$u$is an arbitrary node on locally twisted cube and$n\geq 1$. And the correctness of our algorithm is proved.