On the Longest Fault-Free Paths in Hypercubes with More Faulty Nodes

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Tz-Liang Kueng Articles by Tyne Liang Articles by Jimmy J. M. Tan Articles by Lih-Hsing Hsu

The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008)

May 07-May 09

ISBN: 978-0-7695-3125-0

	ASCII Text	x
	Tz-Liang Kueng, Tyne Liang, Jimmy J. M. Tan, Lih-Hsing Hsu, "On the Longest Fault-Free Paths in Hypercubes with More Faulty Nodes," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 71-76, The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008), 2008.

	BibTex	x
	@article{ 10.1109/I-SPAN.2008.29, author = {Tz-Liang Kueng and Tyne Liang and Jimmy J. M. Tan and Lih-Hsing Hsu}, title = {On the Longest Fault-Free Paths in Hypercubes with More Faulty Nodes}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {2008}, isbn = {978-0-7695-3125-0}, pages = {71-76}, doi = {http://doi.ieeecomputersociety.org/10.1109/I-SPAN.2008.29}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - On the Longest Fault-Free Paths in Hypercubes with More Faulty Nodes SN - 978-0-7695-3125-0 SP71 EP76 A1 - Tz-Liang Kueng, A1 - Tyne Liang, A1 - Jimmy J. M. Tan, A1 - Lih-Hsing Hsu, PY - 2008 KW - Interconnection network KW - Hypercube KW - Conditional fault KW - Linear array KW - Path embedding VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/I-SPAN.2008.29

Faults in a network may take various forms such as hardware/software errors, node/link faults, etc. In this paper, node-faults are addressed. Let F be a faulty set of f ≤ 2n − 6 conditional node-faults in an injured n-cube Qn such that every node of Q_n still has at least two faultfree neighbors. Then we show that Qn − 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 an n-cube is a bipartite graph, such kind of the faultfree path turns out to be the longest one in the case when all faulty nodes belong to the same partite set.

Index Terms:

Interconnection network, Hypercube, Conditional fault, Linear array, Path embedding

Citation:

Tz-Liang Kueng, Tyne Liang, Jimmy J. M. Tan, Lih-Hsing Hsu, "On the Longest Fault-Free Paths in Hypercubes with More Faulty Nodes," ispan, pp.71-76, The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008), 2008

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.