Independent spanning trees in crossed cubes

被引：7

作者：

Zhang, Yan-Hong ^{[1
]}

Hao, Wei ^{[1
]}

Xiang, Tao ^{[2
]}

机构：

[1] Henan Univ Urban Construct, Dept Comp Sci & Engn, Pingdingshan 467036, Henan, Peoples R China

[2] Chongqing Univ, Coll Comp Sci, Chongqing 400044, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 18期

关键词：

Interconnection networks; Crossed cubes; Independent spanning trees; Algorithms; Fault-tolerance; HYPERCUBES; PATH;

D O I：

10.1016/j.ipl.2013.06.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper addresses the independent spanning trees (ISTs) problem in crossed cubes. The algorithm proposed in this paper generates n ISTs for an n-dimensional crossed cube (CQ(n)). This algorithm takes time O (N log N) and can be parallelized to run in time O (log N), where N = 2(n) is the number of the nodes in CQ(n). To the best of our knowledge, this is the first algorithm which can parallelly construct the ISTs in crossed cubes. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：653 / 658

页数：6

共 16 条

[1] Cheng B.-L., 2010, INF SCI ENG ICISE 20, P961
[2] THE CROSSED CUBE ARCHITECTURE FOR PARALLEL COMPUTATION
EFE, K
[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (05) : 513 - 524
[3] Fan J., 2005, INFORM SCI, V176, P3332
[4] Optimal path embedding in crossed cubes
Fan, JX
Lin, XL
Jia, XH
[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (12) : 1190 - 1200
[5] Constructing edge-disjoint spanning trees in locally twisted cubes
Hsieh, Sun-Yuan
Tu, Chang-Jen
[J]. THEORETICAL COMPUTER SCIENCE, 2009, 410 (8-10) : 926 - 932
[6] Huang WT, 2002, IEICE T FUND ELECTR, VE85A, P1359
[7] Fault-free Hamiltonian cycles in crossed cubes with conditional link faults
Hung, Hao-Shun
Fu, Jung-Sheng
Chen, Gen-Huey
[J]. INFORMATION SCIENCES, 2007, 177 (24) : 5664 - 5674
[8] Constructing the nearly shortest path in crossed cubes
Lai, Pao-Lien
Hsu, Hong-Chun
[J]. INFORMATION SCIENCES, 2009, 179 (14) : 2487 - 2493
[9] Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes
Lin, Jia-Cian
Yang, Jinn-Shyong
Hsu, Chiun-Chieh
Chang, Jou-Ming
[J]. INFORMATION PROCESSING LETTERS, 2010, 110 (10) : 414 - 419
[10] Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security
Rescigno, AA
[J]. INFORMATION SCIENCES, 2001, 137 (1-4) : 259 - 276

← 1 2 →