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 条
  • [21] Fault-tolerant edge and vertex pancyclicity in alternating group graphs
    Szepietowski, Andrzej
    APPLIED MATHEMATICS AND COMPUTATION, 2010, 217 (06) : 2827 - 2832
  • [22] Families of optimal fault-tolerant multiple-bus networks
    Tu, HY
    Hawkes, LW
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2001, 12 (01) : 60 - 73
  • [23] Fault-tolerant mechatronic systems, part 1
    Isermann, Rolf
    AT-AUTOMATISIERUNGSTECHNIK, 2007, 55 (04) : 170 - 179
  • [24] Fault-Tolerant Swarms
    Perez, Ivan
    Goodloe, Alwyn
    Edmonson, William
    2019 IEEE INTERNATIONAL CONFERENCE ON SPACE MISSION CHALLENGES FOR INFORMATION TECHNOLOGY (SMC-IT 2019), 2019, : 47 - 54
  • [25] Optimal fault-tolerant design approach for VLSI array processors
    Zhang, CN
    Bachtiar, TM
    Chou, WK
    IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, 1997, 144 (01): : 15 - 21
  • [26] Conditional (edge-)fault-tolerant strong Menger (edge) connectivity of folded hypercubes
    Cheng, Qi
    Li, Pingshan
    Xu, Min
    THEORETICAL COMPUTER SCIENCE, 2018, 728 : 1 - 8
  • [27] EdgeHydra: Fault-Tolerant Edge Data Distribution Based on Erasure Coding
    He, Qiang
    Zhang, Guobiao
    Wang, Jiawei
    Luo, Ruikun
    Dai, Xiaohai
    Hu, Yuchong
    Chen, Feifei
    Jin, Hai
    Yang, Yun
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2025, 36 (01) : 29 - 42
  • [28] Fault-Tolerant Maximal Local-Edge-Connectivity of Augmented Cubes
    Zhai, Liyang
    Xu, Liqiong
    Yang, Weihua
    PARALLEL PROCESSING LETTERS, 2020, 30 (03)
  • [29] Decentralized and Fault-Tolerant Task Offloading for Enabling Network Edge Intelligence
    Zhang, Huixiang
    Liao, Kaihua
    Tai, Yu
    Ma, Wenqiang
    Cao, Guoyan
    Sun, Wen
    Xu, Lexi
    IEEE SYSTEMS JOURNAL, 2024, 18 (02): : 1459 - 1470
  • [30] A Fault-Tolerant Mobility-Aware Caching Method in Edge Computing
    Ma, Yong
    Zhao, Han
    Guo, Kunyin
    Xia, Yunni
    Wang, Xu
    Niu, Xianhua
    Zhu, Dongge
    Dong, Yumin
    CMES-COMPUTER MODELING IN ENGINEERING & SCIENCES, 2024, 140 (01): : 907 - 927
12345