Explicit construction of linear sized tolerant networks

N. Alon, F. R.K. Chung

Research output: Contribution to journalArticlepeer-review

4 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 tolerant linear arrays.

Original languageEnglish (US)
Pages (from-to)1068-1071
Number of pages4
JournalDiscrete Mathematics
Issue number10-11
StatePublished - May 28 2006
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