• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Cheng, Baolei (Cheng, Baolei.) [1] | Fan, Jianxi (Fan, Jianxi.) [2] | Lin, Cheng-Kuan (Lin, Cheng-Kuan.) [3] | Wang, Yan (Wang, Yan.) [4] | Wang, Guijuan (Wang, Guijuan.) [5]

Indexed by:

EI Scopus SCIE

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:

Augmented cube Edge-independent spanning trees Fault-tolerant broadcasting Height

Community:

  • [ 1 ] [Cheng, Baolei]Soochow Univ, Sch Comp Sci & Technol, Suzhou 215006, Peoples R China
  • [ 2 ] [Fan, Jianxi]Soochow Univ, Sch Comp Sci & Technol, Suzhou 215006, Peoples R China
  • [ 3 ] [Wang, Yan]Soochow Univ, Sch Comp Sci & Technol, Suzhou 215006, Peoples R China
  • [ 4 ] [Wang, Guijuan]Soochow Univ, Sch Comp Sci & Technol, Suzhou 215006, Peoples R China
  • [ 5 ] [Cheng, Baolei]Jiangsu High Technol Res Key Lab Wireless Sensor, Nanjing 21000, Jiangsu, Peoples R China
  • [ 6 ] [Fan, Jianxi]Jiangsu High Technol Res Key Lab Wireless Sensor, Nanjing 21000, Jiangsu, Peoples R China
  • [ 7 ] [Lin, Cheng-Kuan]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350116, Peoples R China

Reprint 's Address:

  • [Fan, Jianxi]Soochow Univ, Sch Comp Sci & Technol, Suzhou 215006, Peoples R China

Show more details

Related Keywords:

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:

WoS CC 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

Online/Total:288/11064906
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1