Explicit construction of linear sized tolerant networks

N. Alon, F. R.K. Chung

Research output: Contribution to journalArticlepeer-review

194 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)15-19
Number of pages5
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Dec 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • 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