Fault-tolerant ring embedding in a star graph with both link and node failures

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29197

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29197

Title:	Fault-tolerant ring embedding in a star graph with both link and node failures
Authors:	Tseng,YC;Chang,SH;Sheu,JP
Contributors:	資訊工程研究所
Keywords:	INTERCONNECTION NETWORKS;ALGORITHMS;HYPERCUBES
Date:	1997
Issue Date:	2010-06-29 20:16:07 (UTC+8)
Publisher:	中央大學
Abstract:	The star graph interconnection network has been recognized as an attractive alternative to the hypercube network. Previously, the star graph has been shown to contain a Hamiltonian cycle. In this paper, we consider an injured star graph with some faulty links and nodes. We show that even with f(e) less than or equal to n - 3 faulty links, a Hamiltonian cycle still can be found in an n-star, and that with f(v) less than or equal to n - 3 faulty nodes, a ring containing at most 4f(v) nodes less than that in a Hamiltonian cycle can be found (i.e., the ring contains at least nl - 4f(v) nodes). In general, in an n-star with f(e) faulty links and f(v) faulty nodes, where f(e) + f(v) less than or equal to n - 3, our embedding is able to establish a ring containing at least nl - 4f(v) nodes.
Relation:	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	477	View/Open

社群 sharing