Long paths in hypercubes with conditional node-faults

Tz-Liang Kueng; Tyne Liang; Lih Hsing Hsu; Jiann-Mean Tan

doi:10.1016/j.ins.2008.10.015

Long paths in hypercubes with conditional node-faults

Tz-Liang Kueng, Tyne Liang, Lih Hsing Hsu, Jiann-Mean Tan

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

40 Scopus citations

Abstract

Let F be a set of f <= 2n - 5 faulty nodes in an n-cube Q(n) such that every node of Q(n) still has at least two fault-free neighbors. Then we show that Q(n) - F contains a path of length at least 2(n) - 2f - 1 (respectively, 2(n) - 2f - 2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2(n) - 2f - 1 (or 2(n) - 2f - 2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n - 2 faulty nodes are considered. (c) 2008 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	667-681
Number of pages	15
Journal	Information Sciences
Volume	179
Issue number	5
DOIs	https://doi.org/10.1016/j.ins.2008.10.015
State	Published - 15 Feb 2009

Keywords

Interconnection network; Hypercube; Fault tolerance; Conditional fault; Linear array; Path embedding

Access to Document

10.1016/j.ins.2008.10.015

Fingerprint Dive into the research topics of 'Long paths in hypercubes with conditional node-faults'. Together they form a unique fingerprint.

Cite this

@article{2589eac987fa4d9b941f896ce19cbfa1,

title = "Long paths in hypercubes with conditional node-faults",

abstract = "Let F be a set of f <= 2n - 5 faulty nodes in an n-cube Q(n) such that every node of Q(n) still has at least two fault-free neighbors. Then we show that Q(n) - F contains a path of length at least 2(n) - 2f - 1 (respectively, 2(n) - 2f - 2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2(n) - 2f - 1 (or 2(n) - 2f - 2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n - 2 faulty nodes are considered. (c) 2008 Elsevier Inc. All rights reserved.",

keywords = "Interconnection network; Hypercube; Fault tolerance; Conditional fault; Linear array; Path embedding",

author = "Tz-Liang Kueng and Tyne Liang and Hsu, {Lih Hsing} and Jiann-Mean Tan",

year = "2009",

month = feb,

day = "15",

doi = "10.1016/j.ins.2008.10.015",

language = "English",

volume = "179",

pages = "667--681",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

number = "5",

}

TY - JOUR

T1 - Long paths in hypercubes with conditional node-faults

AU - Kueng, Tz-Liang

AU - Liang, Tyne

AU - Hsu, Lih Hsing

AU - Tan, Jiann-Mean

PY - 2009/2/15

Y1 - 2009/2/15

N2 - Let F be a set of f <= 2n - 5 faulty nodes in an n-cube Q(n) such that every node of Q(n) still has at least two fault-free neighbors. Then we show that Q(n) - F contains a path of length at least 2(n) - 2f - 1 (respectively, 2(n) - 2f - 2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2(n) - 2f - 1 (or 2(n) - 2f - 2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n - 2 faulty nodes are considered. (c) 2008 Elsevier Inc. All rights reserved.

AB - Let F be a set of f <= 2n - 5 faulty nodes in an n-cube Q(n) such that every node of Q(n) still has at least two fault-free neighbors. Then we show that Q(n) - F contains a path of length at least 2(n) - 2f - 1 (respectively, 2(n) - 2f - 2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2(n) - 2f - 1 (or 2(n) - 2f - 2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n - 2 faulty nodes are considered. (c) 2008 Elsevier Inc. All rights reserved.

KW - Interconnection network; Hypercube; Fault tolerance; Conditional fault; Linear array; Path embedding

U2 - 10.1016/j.ins.2008.10.015

DO - 10.1016/j.ins.2008.10.015

M3 - Article

VL - 179

SP - 667

EP - 681

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

IS - 5

ER -