Name
Abstract | ||
|---|---|---|
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. © 2013 Elsevier Inc. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ins.2013.01.010 | Information Sciences |
Keywords | DocType | Volume |
Crossed cube,Fault-tolerant broadcasting,Independent spanning trees,Internally vertex-disjoint paths | Journal | 233 |
ISSN | Citations | PageRank |
00200255 | 21 | 0.60 |
References | Authors | |
41 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng Baolei | 1 | 84 | 2.81 |
| Jianxi Fan | 2 | 718 | 60.15 |
| Xiaohua Jia | 3 | 4609 | 303.30 |
| Zhang Shukui | 4 | 39 | 1.53 |