Name
Abstract | ||
|---|---|---|
For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQ(n) is both (2n - 1)-edge-connected and (2n - 1)-nodeconnected (n not equal 3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQ(n). So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQ(n) is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k - 1 node-ISTs rooted at node 0 in AQ(n)(vertical bar 00...0}/n-k (n >= k >= 4) by proposing an ingenious way of construction and propose a corresponding O(N logN) time algorithm, where N = 2(k) is the number of nodes in AQ(n)(vertical bar 00...0}/n-k. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.3233/FI-2020-1965 | FUNDAMENTA INFORMATICAE |
Keywords | DocType | Volume |
Augmented cubes, node-independent spanning trees, constructive algorithm, secure message distribution | Journal | 176 |
Issue | ISSN | Citations |
2 | 0169-2968 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng Baolei | 1 | 10 | 5.56 |
| Jianxi Fan | 2 | 718 | 60.15 |
| Qiang Lyu | 3 | 0 | 1.01 |
| Cheng-Kuan Lin | 4 | 4 | 1.73 |
| Xiaoyan Li | 5 | 21 | 10.23 |
| Guo Chen | 6 | 1 | 0.69 |