FINDING A TARGET SUBNETWORK IN SPARSE NETWORKS WITH RANDOM FAULTS

Authors
FRAIGNIAUD P KENYON C PELC A
Citation
P. Fraigniaud et al., FINDING A TARGET SUBNETWORK IN SPARSE NETWORKS WITH RANDOM FAULTS, Information processing letters, 48(6), 1993, pp. 297-303
Citations number
12
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
48
Issue
6
Year of publication
1993
Pages
297 - 303
Database
ISI
SICI code
0020-0190(1993)48:6<297:FATSIS>2.0.ZU;2-0
Abstract
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* fa il independently with constant probability p, G almost certainly cont ains a fault-free isomorphic copy of G.