標題: Optimal 1-edge fault-tolerant designs for ladders
作者: Chuang, YC
Hsu, LH
Chang, CH
資訊工程學系
Department of Computer Science
關鍵字: Cartesian product;edge fault tolerance;meshes;ladders;fault tolerance
公開日期: 31-Oct-2002
摘要: A graph G* is 1-edge fault-tolerant with respect to a graph G, denoted by 1-EFT(G), if every graph obtained by removing any edge from G* contains G. A1-EFT(G) graph is optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. The kth ladder graph, L-k, is defined to be the cartesian product of the P-k and P-2 where P-n is the n-vertex path graph. In this paper, we present several 1-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal. (C) 2002 Elsevier Science B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/S0020-0190(02)00225-9
http://hdl.handle.net/11536/28441
ISSN: 0020-0190
DOI: 10.1016/S0020-0190(02)00225-9
期刊: INFORMATION PROCESSING LETTERS
Volume: 84
Issue: 2
起始頁: 87
結束頁: 92
Appears in Collections:Articles


Files in This Item:

  1. 000178093900005.pdf