Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2020

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: node-independent spanning trees

Sortuj według:

Ogranicz wyniki do:

Constructing Node-Independent Spanning Trees in Augmented Cubes

Cheng Baolei, Fan Jianxi, Lyu Qiang, Lin Cheng-Kuan, Li Xiaoyan, Chen Guo

Fundamenta Informaticae

2020

Vol. 176, nr 2

103--128

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 AQn is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n≠3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQn. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQn 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 AQn ( 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 = 2k is the number of nodes in AQn ( 00...0 n – k ) .