Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes

被引：34

作者：

Cheng, Baolei ^{[1
,2
]}

Fan, Jianxi ^{[1
]}

Jia, Xiaohua ^{[3
]}

Wang, Jin ^{[1
]}

机构：

[1] Soochow Univ, Sch Comp Sci & Technol, Suzhou 215006, Peoples R China

[2] Soochow Univ, Prov Key Lab Comp Informat Proc Technol, Suzhou 215006, Peoples R China

[3] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 2013年 / 73卷 / 05期

基金：

中国国家自然科学基金;

关键词：

Crossed cube; Independent spanning tree; Internally disjoint path; Dimension-adjacent tree; Parallel construction; BIJECTIVE CONNECTION GRAPHS; TWISTED CUBES; HYPERCUBES; ALGORITHM; NETWORKS; MESHES; CYCLES; FAMILY; TORUS; PATHS;

D O I：

10.1016/j.jpdc.2013.01.009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Independent spanning trees (ISTs) have increasing applications in fault-tolerance, bandwidth, and security. In this paper, we study the problem of parallel construction of ISTs on crossed cubes. We first propose the definitions of dimension-adjacent walk and dimension-adjacent tree along with a dimension property of crossed cubes. Then, we consider the parallel construction of ISTs on crossed cubes. We show that there exist n general dimension-adjacent trees which are independent of the addresses of vertices in the n-dimensional crossed cube CQ(n). Based on n dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity is O(2(n))proposed to construct n ISTs on CQ(n), where n >= 1. (C) 2013 Elsevier Inc. All rights reserved.

引用

页码：641 / 652

页数：12

共 38 条

[1] Reliable broadcasting in product networks [J].

Bao, F ;

Igarashi, Y ;

Ohring, SR .

DISCRETE APPLIED MATHEMATICS, 1998, 83 (1-3) :3-20

[2]

Bao F, 1998, IEICE T FUND ELECTR, VE81A, P796

[3] Multi-node broadcasting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy [J].

Chen, YS ;

Chiang, CY ;

Chen, CY .

JOURNAL OF SYSTEMS ARCHITECTURE, 2004, 50 (09) :575-589

[4]

Cheng B., 2012, COMPUT J, DOI DOI 10.1093/C0MJ

[5] Independent spanning trees in crossed cubes [J].

Cheng, Baolei ;

Fan, Jianxi ;

Jia, Xiaohua ;

Zhang, Shukui .

INFORMATION SCIENCES, 2013, 233 :276-289

[6] FINDING NONSEPARATING INDUCED CYCLES AND INDEPENDENT SPANNING-TREES IN 3-CONNECTED GRAPHS [J].

CHERIYAN, J ;

MAHESHWARI, SN .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1988, 9 (04) :507-537

[7] Finding four independent trees [J].

Curran, S ;

Lee, O ;

Yu, XX .

SIAM JOURNAL ON COMPUTING, 2006, 35 (05) :1023-1058

[8] Embedding a family of disjoint 3D meshes into a crossed cube [J].

Dong, Qiang ;

Yang, Xiaofan ;

Zhao, Juan ;

Tang, Yuan Yan .

INFORMATION SCIENCES, 2008, 178 (11) :2396-2405

[9] THE CROSSED CUBE ARCHITECTURE FOR PARALLEL COMPUTATION [J].

EFE, K .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (05) :513-524

[10] A VARIATION ON THE HYPERCUBE WITH LOWER DIAMETER [J].

EFE, K .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (11) :1312-1316

← 1 2 3 4 →