Name
Abstract | ||
|---|---|---|
Edge-independent spanning trees (EISTs) have important applications in networks such as reliable communication protocols, one-to-all broadcasting, and secure message distribution, thus their designs in several classes of networks have been widely investigated. The n-dimensional augmented cube (AQn) is an important variant of the n-dimensional hypercube. It is (2n1)-regular, (2n1)-connected (n3), vertex-symmetric and has diameter of n/2. In this paper, by proposing an O(NlogN) algorithm that constructs 2n1 EISTs in AQn, where N is the number of nodes in AQn, we solve the EISTs problem for this class of graphs. Since AQn is (2n1)-regular, the result is optimal with respect to the number of EISTs constructed. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2017.01.016 | Theor. Comput. Sci. |
Keywords | Field | DocType |
Edge independent spanning trees,Augmented cubes,Algorithm,Fault -tolerance | Discrete mathematics,Graph,Broadcasting,Combinatorics,Independent spanning trees,Fault tolerance,Spanning tree,Hypercube,Mathematics,Communications protocol,Cube | Journal |
Volume | Issue | ISSN |
670 | C | 0304-3975 |
Citations | PageRank | References |
3 | 0.38 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yan Wang | 1 | 4 | 2.08 |
| Hong Shen | 2 | 107 | 27.61 |
| Jianxi Fan | 3 | 718 | 60.15 |