Explicit Construction of Linear Sized Tolerant Networks

N. Alon, F. R.K. Chung

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)15-19
Number of pages5
JournalAnnals of Discrete Mathematics
Issue numberC
StatePublished - Jan 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Explicit Construction of Linear Sized Tolerant Networks'. Together they form a unique fingerprint.

Cite this