Long paths in hypercubes with conditional node-faults

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

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)667-681
Number of pages15
JournalInformation Sciences
Volume179
Issue number5
DOIs
StatePublished - 15 Feb 2009

Keywords

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

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

  • Cite this

    Kueng, T-L., Liang, T., Hsu, L. H., & Tan, J-M. (2009). Long paths in hypercubes with conditional node-faults. Information Sciences, 179(5), 667-681. https://doi.org/10.1016/j.ins.2008.10.015