標題: Faithful 1-edge fault tolerant graphs
作者: Wang, SY
Hsu, LH
Sung, TY
資訊工程學系
Department of Computer Science
關鍵字: Cartesian product;Kronecker product;edge fault tolerance;meshes;tori
公開日期: 28-二月-1997
摘要: A graph G* is 1-edge fault tolerant with respect to a graph G, denoted by 1-EFT(G), if any graph obtained by removing an edge from G* contains G. A 1-EFT(G) graph is said to be optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. Let G(i)* be 1-EFT(G(i)) for i = 1,2. It can be easily verified that the cartesian product graph G(1)* x G(2)* is 1-edge fault tolerant with respect to the cartesian product graph G(1) x G(2). However, G(1)* x G(2)* may contain too many edges; hence it may nor be optimal for many cases. In this paper, we introduce the concept of faithful graph with respect to a given graph, which is proved to be 1-edge fault tolerant. Based on this concept, we present a construction method of the 1-EFT graph for the cartesian product of several graphs. Applying this construction scheme, we can obtain optimal 1-edge fault tolerant graphs with respect to n-dimensional tori C(m(1), m(2),...,m(n)), where m(i) greater than or equal to 4 are even integers for all 1 less than or equal to i less than or equal to n. (C) 1997 Elsevier Science B.V.
URI: http://hdl.handle.net/11536/717
ISSN: 0020-0190
期刊: INFORMATION PROCESSING LETTERS
Volume: 61
Issue: 4
起始頁: 173
結束頁: 181
顯示於類別:期刊論文


文件中的檔案:

  1. A1997WP28400001.pdf