Optimal 1-edge fault-tolerant designs for ladders

被引：5
作者：
Chuang, YC
Hsu, LH [1 ]
Chang, CH
机构：
[1] Natl Chiao Tung Univ, Dept Comp & Informat Sci, Hsinchu 30050, Taiwan
[2] Ming Hsin Inst Technol, Hsinchu, Taiwan
来源：
INFORMATION PROCESSING LETTERS | 2002年 / 84卷 / 02期
关键词：
Cartesian product; edge fault tolerance; meshes; ladders; fault tolerance;
D O I：
10.1016/S0020-0190(02)00225-9
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：87 / 92
页数：6
相关论文
共 50 条
  • [1] Faithful 1-edge fault tolerant graphs
    Wang, SY
    Hsu, LH
    Sung, TY
    INFORMATION PROCESSING LETTERS, 1997, 61 (04) : 173 - 181
  • [2] Formal Verification of Fault-Tolerant Hardware Designs
    Entrena, Luis
    Sanchez-Clemente, Antonio J.
    Garcia-Astudillo, Luis A.
    Portela-Garcia, Marta
    Garcia-Valderas, Mario
    Lindoso, Almudena
    Sarmiento, Roberto
    IEEE ACCESS, 2023, 11 : 116127 - 116140
  • [3] Fault-tolerant designs in lattice networks on the Klein bottle
    Shabbir, Ayesha
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2014, 2 (02) : 99 - 109
  • [4] A Methodology for Fault-tolerant Pareto-optimal Approximate Designs of FPGA-based Accelerators
    Tsounis, Ioannis
    Agiakatsikas, Dimitris
    Psarakis, Mihalis
    ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2023, 22 (04)
  • [5] OPTIMAL FAULT-TOLERANT ROUTINGS FOR CONNECTED GRAPHS
    WADA, K
    LUO, Y
    KAWAGUCHI, K
    INFORMATION PROCESSING LETTERS, 1992, 41 (03) : 169 - 174
  • [6] CEFIoT: A Fault-Tolerant IoT Architecture for Edge and Cloud
    Javed, Asad
    Heljanko, Keijo
    Buda, Andrea
    Framling, Kary
    2018 IEEE 4TH WORLD FORUM ON INTERNET OF THINGS (WF-IOT), 2018, : 813 - 818
  • [7] Reliable and Fault-Tolerant IoT-Edge Architecture
    Grover, Jitender
    Garimella, Rama Murthy
    2018 IEEE SENSORS, 2018, : 609 - 612
  • [8] Edge-Version of Fault-Tolerant Resolvability in Networks
    Faheem, Muhammad
    Ahmad, Muhammad
    Zahid, Zohaib
    Javaid, Muhammad
    Ashebo, Mamo Abebe
    IEEE ACCESS, 2025, 13 : 3601 - 3612
  • [9] Optimal Fault-tolerant Broadcasting in Wireless Mesh Networks
    Xin, Qin
    Zhang, Yan
    2008 INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE SWITCHING AND ROUTING (HPSR), 2008, : 38 - 44
  • [10] Optimal correction of concatenated fault-tolerant quantum codes
    Z. W. E. Evans
    A. M. Stephens
    Quantum Information Processing, 2012, 11 : 1511 - 1521
12345