کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
393171 | 665574 | 2013 | 14 صفحه PDF | دانلود رایگان |
Multiple independent spanning trees (ISTs) can be used for data broadcasting in networks, which can provide advantageous performances, such as the enhancement of fault-tolerance, bandwidth, and security. However, there is a conjecture on the existence of ISTs in graphs: If a graph G is n-connected (n ⩾ 1), then there are n ISTs rooted at an arbitrary vertex in G. This conjecture has remained open for n ⩾ 5. The n-dimensional crossed cube CQn is a n-connected graph with various desirable properties, which is an important variant of the n-dimensional hypercube. In this paper, we study the existence and construction of ISTs in crossed cubes. We first give a proof of the existence of n ISTs rooted at an arbitrary vertex in CQn(n ⩾ 1). Then, we propose an O(N log2N) constructive algorithm, where N = 2n is the number of vertices in CQn.
Journal: Information Sciences - Volume 233, 1 June 2013, Pages 276–289