TY - JOUR

T1 - Explicit construction of linear sized tolerant networks

AU - Alon, N.

AU - Chung, F. R.K.

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

PY - 1988/12

Y1 - 1988/12

N2 - For every ε{lunate} > 0 and every integer m > 0, we construct explicitly graphs with O(m/ε{lunate}) vertices and maximum degree O( 1 ε{lunate}2), such that after removing any (1 - ε{lunate}) 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 ε{lunate} > 0 and every integer m > 0, we construct explicitly graphs with O(m/ε{lunate}) vertices and maximum degree O( 1 ε{lunate}2), such that after removing any (1 - ε{lunate}) 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=38249028223&partnerID=8YFLogxK

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

U2 - 10.1016/0012-365X(88)90189-6

DO - 10.1016/0012-365X(88)90189-6

M3 - Article

AN - SCOPUS:38249028223

VL - 72

SP - 15

EP - 19

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -