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 条
  • [31] UNION: Fault-tolerant Cooperative Computing in Opportunistic Mobile Edge Cloud
    Xiao, Wenhua
    Fang, Xudong
    Liu, Bixin
    Wang, Ji
    Zhu, Xiaomin
    ACM TRANSACTIONS ON INTERNET TECHNOLOGY, 2023, 23 (04)
  • [32] Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model
    Yang, Da-Wei
    Feng, Yan-Quan
    Kwak, Jin Ho
    Zhou, Jin-Xin
    INFORMATION SCIENCES, 2016, 329 : 317 - 328
  • [33] Adoption Protocols for Fanout-Optimal Fault-Tolerant Termination Detection
    Lifflander, Jonathan
    Miller, Phil
    Kale, Laxmikant V.
    ACM SIGPLAN NOTICES, 2013, 48 (08) : 13 - 22
  • [34] Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed, and Parallel
    Parter, Merav
    PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22), 2022, : 1080 - 1092
  • [35] An efficient reconfiguration scheme for fault-tolerant meshes
    Chuang, PJ
    Yao, LC
    INFORMATION SCIENCES, 2005, 172 (3-4) : 309 - 333
  • [36] PreGAN: Preemptive Migration Prediction Network for Proactive Fault-Tolerant Edge Computing
    Tuli, Shreshth
    Casale, Giuliano
    Jennings, Nicholas R.
    IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (IEEE INFOCOM 2022), 2022, : 670 - 679
  • [37] Fault-tolerant PACS server
    Cao, F
    Liu, BJ
    Huang, HK
    Zhou, MZ
    Zhang, J
    Zhang, X
    Mogel, G
    MEDICAL IMAGING 2002: PACS AND INTEGRATED MEDICAL INFORMATION SYSTEMS: DESIGN AND EVALUATION, 2002, 4685 : 316 - 325
  • [38] Fault-Tolerant Strong Menger (Edge) Connectivity of DCC Linear Congruential Graphs
    Yu, Zhengqin
    Zhou, Shuming
    Zhang, Hong
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2022, 33 (08) : 1019 - 1032
  • [39] Fault-Tolerant Mechanism for Edge-Based IoT Networks With Demand Uncertainty
    Samanta, Amit
    Esposito, Flavio
    Tri Gia Nguyen
    IEEE INTERNET OF THINGS JOURNAL, 2021, 8 (23) : 16963 - 16971
  • [40] Color Fault-Tolerant Spanners
    Petruschka, Asaf
    Sapir, Shay
    Tzalik, Elad
    15TH INNOVATIONS IN THEORETICAL COMPUTER SCIENCE CONFERENCE, ITCS 2024, 2024,
12345