Indexed by:
Abstract:
Edge-Independent spanning trees (EISTs) can be used in IP fast rerouting to guarantee recovery from link failures, as well as in data broadcasting in networks to enhance fault-tolerance, bandwidth, and security. The n-dimensional augmented cube AQ(n) is an important node-symmetric variant of the n-dimensional hypercube Q(n). Recently, Wang et al. proposed a method to construct 2n - 1 EISTs in AQ(n), (Wang et al., 2017). However, the height of the tallest EIST is no less than n+2. Since height is an important performance indicator of the EISTs, in this paper, we further study the existence and construction of EISTs in augmented cubes with lower heights. We first propose a constructive algorithm to construct 2n - 1 trees rooted at any node in AQ(n). We then prove the 2n - 1 trees obtained by the algorithm are 2n - 1 EISTs with the maximal height n, and the time complexity of the algorithm is O(N log N), where N = 2(n) is the number of nodes in AQ(n). (C) 2019 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE APPLIED MATHEMATICS
ISSN: 0166-218X
Year: 2020
Volume: 277
Page: 55-70
1 . 1 3 9
JCR@2020
1 . 0 0 0
JCR@2023
ESI Discipline: ENGINEERING;
ESI HC Threshold:132
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count: 9
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: