An algorithm to construct independent spanning trees on crossed cubes
Baolei Cheng, Jianxi Fan, Jiwen Yang, Yuejuan Han · 2010
The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, such as the increase of fault-tolerance, bandwidth. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. Some results have been found on the hypercube and its variations such as the folded cube, the twisted cube, and the locally twisted cube, etc. The crossed cube is an important variant of the hypercube which has attracted much attention from researchers. In this paper, we proposed an O(NlogN) algorithm to construct n independent spanning trees rooted at any vertex u similar to 0nor vertex 0non the n-dimentional crossed cube CQn, where N = 2n. Our algorithm can be applied to 2⌈n/2⌉vertices in CQn.