TY - JOUR

T1 - Explicit Construction of Linear Sized Tolerant Networks

AU - Alon, N.

AU - Chung, F. R.K.

N1 - Funding Information:
Research supported in part by Allon Fellowship and by the fund for basic research administered by the Israel Academy of Sciences.

PY - 1988/1/1

Y1 - 1988/1/1

N2 - For every ɛ0 and every integer m0, we construct explicitly graphs with O(mɛ vertices and maximum degree O(1ɛ2), such that after removing any (1-ɛ) portion of their vertices or edges, the remaining graph still contains a path of length m. This settles a problem of Rosenberg, which was motivated by the study of fault torerant linear arrays.

AB - For every ɛ0 and every integer m0, we construct explicitly graphs with O(mɛ vertices and maximum degree O(1ɛ2), such that after removing any (1-ɛ) portion of their vertices or edges, the remaining graph still contains a path of length m. This settles a problem of Rosenberg, which was motivated by the study of fault torerant linear arrays.

UR - http://www.scopus.com/inward/record.url?scp=77957074439&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957074439&partnerID=8YFLogxK

U2 - 10.1016/S0167-5060(08)70766-0

DO - 10.1016/S0167-5060(08)70766-0

M3 - Article

AN - SCOPUS:77957074439

VL - 38

SP - 15

EP - 19

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

SN - 0167-5060

IS - C

ER -