FINDING A TARGET SUBNETWORK IN SPARSE NETWORKS WITH RANDOM FAULTS

被引：4
|
作者：
FRAIGNIAUD, P [1 ]
KENYON, C [1 ]
PELC, A [1 ]
机构：
[1] UNIV QUEBEC,DEPT INFORMAT,HULL J8X 3X7,PQ,CANADA
来源：
INFORMATION PROCESSING LETTERS | 1993年 / 48卷 / 06期
基金：
加拿大自然科学与工程研究理事会;
关键词：
FAULT TOLERANCE; RANDOM GRAPH;
D O I：
10.1016/0020-0190(93)90172-6
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Given a network G = (V, E) we look for sparse extensions G* = (V*, E*) of G with \V*\is an element of O(\V\) and such that if nodes of G* fail independently with constant probability p, G* almost certainly contains a fault-free isomorphic copy of G.
引用
收藏
页码：297 / 303
页数：7
相关论文
共 50 条
  • [1] Sparse networks tolerating random faults
    Yamada, T
    Ueno, S
    FOURTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS, AND NETWORKS (I-SPAN'99), PROCEEDINGS, 1999, : 114 - 118
  • [2] Sparse networks tolerating random faults
    Yamada, T
    Nomura, K
    Ueno, S
    DISCRETE APPLIED MATHEMATICS, 2004, 137 (02) : 223 - 235
  • [3] Sparse networks tolerating random faults
    Yamada, Toshinori
    Ueno, Shuichi
    Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, 1999, : 114 - 118
  • [4] Sparse networks tolerating random faults for tree-like and butterfly-like networks
    Nomura, K
    Yamada, T
    Ueno, S
    2000 IEEE ASIA-PACIFIC CONFERENCE ON CIRCUITS AND SYSTEMS: ELECTRONIC COMMUNICATION SYSTEMS, 2000, : 799 - 802
  • [5] Finding communities in sparse networks
    Singh, Abhinav
    Humphries, Mark D.
    SCIENTIFIC REPORTS, 2015, 5
  • [6] Finding communities in sparse networks
    Abhinav Singh
    Mark D. Humphries
    Scientific Reports, 5
  • [7] FINDING HAMILTON CYCLES IN SPARSE RANDOM GRAPHS
    FRIEZE, AM
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 44 (02) : 230 - 250
  • [8] Packing and finding paths in sparse random graphs
    Iršič, Vesna
    Portier, Julien
    Versteegen, Leo
    arXiv,
  • [9] THE DYNAMICS OF SPARSE RANDOM NETWORKS
    MINAI, AA
    LEVY, WB
    BIOLOGICAL CYBERNETICS, 1993, 70 (02) : 177 - 187
  • [10] Finding mesoscopic communities in sparse networks
    Ispolatov, I.
    Mazo, I.
    Yuryev, A.
    JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2006,
12345