Explicit Construction of Linear Sized Tolerant Networks

N. Alon, F. R.K. Chung

Research output: Contribution to journalArticle

26 Scopus citations

Abstract

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
Volume38
Issue numberC
DOIs
StatePublished - Jan 1 1988

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

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

  • Cite this