A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks

The line graphs of some well-known graphs, such as the generalized hypercube and the crossed cube, have been adopted for the logic graphs of data center networks (DCNs). Conditional bijective connection networks (conditional BC networks) are a class of networks which have been proved to include hypercubes, crossed cubes, locally twisted cubes and Mobius cubes, etc. Hence, the researches on the line graphs of conditional BC networks can be applied to DCNs. Edge independent spanning trees (EISTs) on a graph have received extensive attention because of their applications in reliable communication, fault-tolerant broadcasting and secure message distribution. Since the line graph of an n- dimensional conditional BC network, denoted as L(XCn), is (2n - 2)-regular, whether there exist 2n - 2 EISTs on L(XCn) is an open question. In this paper, we first propose a parallel algorithm to construct 2n - 2 EISTs rooted at an arbitrary node on L(XCn), where n >= 2. Then, we prove the correctness of our algorithm. Finally, we give a simulation result of our algorithm.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper investigates the application of line graphs of conditional BC networks in data center networks. The authors propose a parallel algorithm to construct 2n - 2 edge independent spanning trees (EISTs) rooted at an arbitrary node on L(XCn), and prove the correctness of the algorithm. Finally, a simulation result of the algorithm is provided.