Longest fault-free paths in hypercubes with both faulty nodes and edges

Sun Yuan Hsieh; Che Nan Kuo; Hui Ling Huang

doi:10.1109/fgcn.2007.163

Longest fault-free paths in hypercubes with both faulty nodes and edges

Sun Yuan Hsieh, Che Nan Kuo, Hui Ling Huang

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The hypercube is one of the most versatile and efficient interconnection networks for parallel computation. Let F_v (respectively, F _e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that Q_n - F_v - F_e contains a fault free path with length at least 2ⁿ - 2|F_v| - 1 (or 2ⁿ - 2|F_v| - 2) between two arbitrary vertices of odd (or even) distance if |F_v| + |F_e| ≤ n - 2, where n > 3. Since Q_n is bipartite of equal-size partite sets, the path is longest in the worst case. Furthermore, since Q_n is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free path obtained are worst-case optimal.

Original language	English
Title of host publication	Proceedings of Future Generation Communication and Networking, FGCN 2007
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	605-608
Number of pages	4
ISBN (Print)	0769530486, 9780769530482
DOIs	https://doi.org/10.1109/fgcn.2007.163
Publication status	Published - 2007
Event	2007 International Conference on Future Generation Communication and Networking, FGCN 2007 - Jeju Island, Korea, Republic of Duration: 2007 Dec 6 → 2007 Dec 8

Publication series

Name	Proceedings of Future Generation Communication and Networking, FGCN 2007
Volume	2

Other

Other	2007 International Conference on Future Generation Communication and Networking, FGCN 2007
Country	Korea, Republic of
City	Jeju Island
Period	07-12-06 → 07-12-08

All Science Journal Classification (ASJC) codes

Computer Science Applications
Software
Electrical and Electronic Engineering

Access to Document

10.1109/fgcn.2007.163

Cite this

Hsieh, S. Y., Kuo, C. N., & Huang, H. L. (2007). Longest fault-free paths in hypercubes with both faulty nodes and edges. In Proceedings of Future Generation Communication and Networking, FGCN 2007 (pp. 605-608). [4426314] (Proceedings of Future Generation Communication and Networking, FGCN 2007; Vol. 2). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/fgcn.2007.163

@inproceedings{daf73c6b487a495f809b043fd44d4344,

title = "Longest fault-free paths in hypercubes with both faulty nodes and edges",

abstract = "The hypercube is one of the most versatile and efficient interconnection networks for parallel computation. Let Fv (respectively, F e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Qn. In this paper, we show that Qn - Fv - Fe contains a fault free path with length at least 2n - 2|Fv| - 1 (or 2n - 2|Fv| - 2) between two arbitrary vertices of odd (or even) distance if |Fv| + |Fe| ≤ n - 2, where n > 3. Since Qn is bipartite of equal-size partite sets, the path is longest in the worst case. Furthermore, since Qn is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free path obtained are worst-case optimal.",

author = "Hsieh, {Sun Yuan} and Kuo, {Che Nan} and Huang, {Hui Ling}",

year = "2007",

doi = "10.1109/fgcn.2007.163",

language = "English",

isbn = "0769530486",

series = "Proceedings of Future Generation Communication and Networking, FGCN 2007",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "605--608",

booktitle = "Proceedings of Future Generation Communication and Networking, FGCN 2007",

address = "United States",

note = "2007 International Conference on Future Generation Communication and Networking, FGCN 2007 ; Conference date: 06-12-2007 Through 08-12-2007",

}

Hsieh, SY, Kuo, CN & Huang, HL 2007, Longest fault-free paths in hypercubes with both faulty nodes and edges. in Proceedings of Future Generation Communication and Networking, FGCN 2007., 4426314, Proceedings of Future Generation Communication and Networking, FGCN 2007, vol. 2, Institute of Electrical and Electronics Engineers Inc., pp. 605-608, 2007 International Conference on Future Generation Communication and Networking, FGCN 2007, Jeju Island, Korea, Republic of, 07-12-06. https://doi.org/10.1109/fgcn.2007.163

Longest fault-free paths in hypercubes with both faulty nodes and edges. / Hsieh, Sun Yuan; Kuo, Che Nan; Huang, Hui Ling.

Proceedings of Future Generation Communication and Networking, FGCN 2007. Institute of Electrical and Electronics Engineers Inc., 2007. p. 605-608 4426314 (Proceedings of Future Generation Communication and Networking, FGCN 2007; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Longest fault-free paths in hypercubes with both faulty nodes and edges

AU - Hsieh, Sun Yuan

AU - Kuo, Che Nan

AU - Huang, Hui Ling

PY - 2007

Y1 - 2007

N2 - The hypercube is one of the most versatile and efficient interconnection networks for parallel computation. Let Fv (respectively, F e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Qn. In this paper, we show that Qn - Fv - Fe contains a fault free path with length at least 2n - 2|Fv| - 1 (or 2n - 2|Fv| - 2) between two arbitrary vertices of odd (or even) distance if |Fv| + |Fe| ≤ n - 2, where n > 3. Since Qn is bipartite of equal-size partite sets, the path is longest in the worst case. Furthermore, since Qn is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free path obtained are worst-case optimal.

AB - The hypercube is one of the most versatile and efficient interconnection networks for parallel computation. Let Fv (respectively, F e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Qn. In this paper, we show that Qn - Fv - Fe contains a fault free path with length at least 2n - 2|Fv| - 1 (or 2n - 2|Fv| - 2) between two arbitrary vertices of odd (or even) distance if |Fv| + |Fe| ≤ n - 2, where n > 3. Since Qn is bipartite of equal-size partite sets, the path is longest in the worst case. Furthermore, since Qn is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free path obtained are worst-case optimal.

UR - http://www.scopus.com/inward/record.url?scp=52249099509&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52249099509&partnerID=8YFLogxK

U2 - 10.1109/fgcn.2007.163

DO - 10.1109/fgcn.2007.163

M3 - Conference contribution

AN - SCOPUS:52249099509

SN - 0769530486

SN - 9780769530482

T3 - Proceedings of Future Generation Communication and Networking, FGCN 2007

SP - 605

EP - 608

BT - Proceedings of Future Generation Communication and Networking, FGCN 2007

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2007 International Conference on Future Generation Communication and Networking, FGCN 2007

Y2 - 6 December 2007 through 8 December 2007

ER -

Hsieh SY, Kuo CN, Huang HL. Longest fault-free paths in hypercubes with both faulty nodes and edges. In Proceedings of Future Generation Communication and Networking, FGCN 2007. Institute of Electrical and Electronics Engineers Inc. 2007. p. 605-608. 4426314. (Proceedings of Future Generation Communication and Networking, FGCN 2007). https://doi.org/10.1109/fgcn.2007.163