Embedding paths of variable lengths into hypercubes with conditional link-faults

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

doi:10.1016/j.parco.2009.06.002

Embedding paths of variable lengths into hypercubes with conditional link-faults

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

Department of Computer Science

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

15 Scopus citations

Abstract

Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q(n), in which every node is still incident to at least two fault-free links. Then we show that Q(n) - F has a path of any odd (resp. even) length in the range from the distance to 2(n) - 1 (resp. 2(n) - 2) between two arbitrary nodes even if vertical bar F vertical bar = 2n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. (C) 2009 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	441-454
Number of pages	14
Journal	Parallel Computing
Volume	35
Issue number	8-9
DOIs	https://doi.org/10.1016/j.parco.2009.06.002
State	Published - Aug 2009

Keywords

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

Access to Document

10.1016/j.parco.2009.06.002

Fingerprint Dive into the research topics of 'Embedding paths of variable lengths into hypercubes with conditional link-faults'. Together they form a unique fingerprint.

Cite this

@article{6c3101d032cf4fc8a31a90661c2ec043,

title = "Embedding paths of variable lengths into hypercubes with conditional link-faults",

abstract = "Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q(n), in which every node is still incident to at least two fault-free links. Then we show that Q(n) - F has a path of any odd (resp. even) length in the range from the distance to 2(n) - 1 (resp. 2(n) - 2) between two arbitrary nodes even if vertical bar F vertical bar = 2n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. (C) 2009 Elsevier B.V. All rights reserved.",

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

author = "Tz-Liang Kueng and Cheng-Kuan Lin and Tyne Liang and Jiann-Mean Tan and Lih-Hsing Hsu",

year = "2009",

month = aug,

doi = "10.1016/j.parco.2009.06.002",

language = "English",

volume = "35",

pages = "441--454",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier",

number = "8-9",

}

TY - JOUR

T1 - Embedding paths of variable lengths into hypercubes with conditional link-faults

AU - Kueng, Tz-Liang

AU - Lin, Cheng-Kuan

AU - Liang, Tyne

AU - Tan, Jiann-Mean

AU - Hsu, Lih-Hsing

PY - 2009/8

Y1 - 2009/8

N2 - Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q(n), in which every node is still incident to at least two fault-free links. Then we show that Q(n) - F has a path of any odd (resp. even) length in the range from the distance to 2(n) - 1 (resp. 2(n) - 2) between two arbitrary nodes even if vertical bar F vertical bar = 2n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. (C) 2009 Elsevier B.V. All rights reserved.

AB - Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q(n), in which every node is still incident to at least two fault-free links. Then we show that Q(n) - F has a path of any odd (resp. even) length in the range from the distance to 2(n) - 1 (resp. 2(n) - 2) between two arbitrary nodes even if vertical bar F vertical bar = 2n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. (C) 2009 Elsevier B.V. All rights reserved.

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

U2 - 10.1016/j.parco.2009.06.002

DO - 10.1016/j.parco.2009.06.002

M3 - Article

VL - 35

SP - 441

EP - 454

JO - Parallel Computing

JF - Parallel Computing

SN - 0167-8191

IS - 8-9

ER -