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 span-ning 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,relia-ble 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 AQn is a node-symmetric variation of the n-dimensional hypercube Qn,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 2n-1 trees rooted at any node in AQn.Then,it proves that the 2n-1 trees obtained by algorithms are EISTs with the height n,and the algorithms'time complexity is O(N),where N equals the number of nodes in AQn.Finally,its accura-cy is verified by simulation experiment.
万方数据
维普
