Path embeddings in faulty 3-ary n-cubes

被引：26

作者：

Wang, Shiying ^{[1
]}

Lin, Shangwei ^{[1
]}

机构：

[1] Shanxi Univ, Sch Math Sci, Taiyuan 030006, Shanxi, Peoples R China

来源：

INFORMATION SCIENCES | 2010年 / 180卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Interconnection networks; k-Ary n-cubes; Fault-tolerance; Path embeddings; Cycle embeddings; Panconnectivity; LINEAR-ARRAY; CROSSED CUBES; HYPERCUBE; GRAPHS;

D O I：

10.1016/j.ins.2009.09.007

中图分类号：

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

学科分类号：

0812 ;

摘要：

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. In this paper, we study the problem of embedding paths of various lengths into faulty 3-ary n-cubes and prove that a faulty 3-ary n-cube with f <= 2n - 3 faulty vertices admits a path of every length from 2n - 1 to 3(n) - f - 1 connecting any two distinct healthy vertices. This result is optimal with respect to the number of vertex faults tolerated. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：191 / 197

页数：7

共 19 条

[1]

[Anonymous], IEEE MICRO

[2]

[Anonymous], P 38 IEEE COMP SOC I

[3] Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes [J].

Ashir, YA ;

Stewart, IA .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (03) :317-328

[4] ON THE K-ARY HYPERCUBE [J].

BETTAYEB, S .

THEORETICAL COMPUTER SCIENCE, 1995, 140 (02) :333-339

[5] LEE DISTANCE AND TOPOLOGICAL PROPERTIES OF K-ARY N-CUBES [J].

BOSE, B ;

BROEG, B ;

KWON, Y ;

ASHIR, Y .

IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (08) :1021-1030

[6] Fast sorting algorithms on a linear array with a reconfigurable pipelined bus system [J].

Datta, A ;

Soundaralakshmi, S ;

Owens, R .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2002, 13 (03) :212-222

[7] Embedding meshes into crossed cubes [J].

Fan, Jianxi ;

Jia, Xiaohua .

INFORMATION SCIENCES, 2007, 177 (15) :3151-3160

[8] Complete path embeddings in crossed cubes [J].

Fan, Jianxi ;

Jia, Xiaohua ;

Lin, Xiaola .

INFORMATION SCIENCES, 2006, 176 (22) :3332-3346

[9] Longest fault-free paths in hypercubes with vertex faults [J].

Fu, JS .

INFORMATION SCIENCES, 2006, 176 (07) :759-771

[10] Panconnectivity and edge-pancyclicity of 3-ary N-cubes [J].

Hsieh, Sun-Yuan ;

Lin, Tsong-Jie ;

Huang, Hui-Ling .

JOURNAL OF SUPERCOMPUTING, 2007, 42 (02) :225-233

← 1 2 →