• 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] | Jia, Xiaohua (Jia, Xiaohua.) [4] | Li, Xiaoyan (Li, Xiaoyan.) [5] (Scholars:李小燕)

Indexed by:

EI Scopus SCIE

Abstract:

Due to the application in reliable communication, reliable broadcasting, secure message distribution, etc., node/edge-independent spanning trees (ISTs) have attracted much attention in the past twenty years. However, node/edge conjecture is still open for networks with node/edge-connectivity >= 5. So far, results have been obtained on a lot of special networks, but only a few results are reported on the line graphs of them. Hypercubes play important roles in parallel computing systems, and the line graphs of which have been recently adopted for the architectures of data center networks. Since the line graph of n-dimensional hypercube Q(n), L(Q(n)), is (2n - 2)-regular, whether there exist 2n - 2 node-ISTs rooted at any node on L(Q(n)) is an open question. In this paper, we focus on the problem of constructing node-ISTs on L(Q(n)). Firstly, we point out that L(Q(n)) can be partitioned into 2(n-1) complete graphs. Then, based on the complete graphs and n - 1 node-ISTs rooted at 0 on Q(n-1)(0), we obtain an "independent forest" containing 2n - 2 trees on L(Q(n)). Furthermore, we present an O(N) time algorithm to construct 2n - 2 node-ISTs rooted at node [0, 2(n-1)] isomorphic to each other on L(Q(n)) based on the independent forest, where N = n x 2(n-1) is the number of nodes on L(Q(n)). In addition, we point out that the 2n - 2 node-ISTs on L(Q(n)) is a new method to prove the node/edge-connectivity and the upper bound of (2n - 2)-node/edge-wide-diameter of L(Q(n)). (C) 2019 Elsevier Inc. All rights reserved.

Keyword:

Independent forest Line graph Network Node-disjoint paths Node-independent spanning trees

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 ] [Cheng, Baolei]Jiangsu High Technol Res Key Lab Wireless Sensor, Nanjing 21000, Jiangsu, Peoples R China
  • [ 4 ] [Fan, Jianxi]Jiangsu High Technol Res Key Lab Wireless Sensor, Nanjing 21000, Jiangsu, Peoples R China
  • [ 5 ] [Lin, Cheng-Kuan]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350116, Fujian, Peoples R China
  • [ 6 ] [Li, Xiaoyan]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350116, Fujian, Peoples R China
  • [ 7 ] [Jia, Xiaohua]City Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China
  • [ 8 ] [Li, Xiaoyan]City Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China

Reprint 's Address:

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

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

ISSN: 0743-7315

Year: 2019

Volume: 134

Page: 104-115

2 . 2 9 6

JCR@2019

3 . 4 0 0

JCR@2023

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:162

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 6

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Online/Total:78/10045529
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