Parallel Construction of Edge-independent Spanning Trees in Augmented Cubes

In recent years,more and more research work is being conducted around interconnected networks.Independent spanning trees(ISTs) can be used in reliable transmission,parallel transmission,safe distribution of information,and parallel diagnosis of fault servers,and have attracted many researchers' attention.In network communication,such as one-to-all broadcasting,reliable communication,multi-node broadcasting,fault-tolerant broadcasting,secure message distribution,and IP fast rerouting,edge-independent spanning trees(EISTs) play a significant role.The augmented cube of n dimension <i>AQ_n</i> is a node-symmetric variation of the <i>n-</i>dimensional hypercube <i>Q_n</i>,it has some embeddable properties that the hypercube and its variants do not have.However,the current EISTs construction methods in augmented cubes are serial construction.This paper first proposes parallel algorithms for constructing <i>2n－1</i> trees rooted at any node in <i>AQ_n</i>.Then,it proves that the <i>2n－1</i> trees obtained by algorithms are EISTs with the height <i>n,</i>and the algorithms' time complexity is O<i>(N)</i>,where <i>N </i>equals the number of nodes in <i>AQ_n</i>.Finally,its accuracy is verified by simulation experiment.