Find in Library

As the foundation of cloud computing technology,the communication performance of data center networks has become a research hotspot in recent years.And as an important infrastructure of data center networks,independent spanning trees(ISTs) attract much attention of researchers because of their application in reliable communication,fault-tolerant broadcasting and secure message distribution,and remarkable results have been obtained on some special networks.But only a few results are reported on the line graphs.A new server-centric network called BCDC was proposed in 2018.Its logic graph is the line graph of crossed cube and is (2<i>n</i>－2)-regular.In this paper,an algorithm is proposed to construct the independent spanning trees on BCDC.Firstly,<i>2n</i>－2 trees are constructed by a parallel algorithm on crossed cube.Then,connect these trees by a special rule,and transfer these trees into 2<i>n</i>－2 independent trees on BCDC through a way of transformation.Finally,the rest nodes of BCDC are connected to these trees by an algorithm which is proposed with time complexity O(<i>N</i>),where <i>N</i> is the number of nodes on BCDC.As a result,we will obtain 2<i>n</i>－2 ISTs rooted at node <i>[ r,N(r,2)]</i> on BCDC,where <i>r</i> is an arbitrary node in <i>n</i> dimensional crossed cube <i>CQ_n</i>.