Explicit construction of linear sized tolerant networks

N. Alon, F. R.K. Chung

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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
Volume306
Issue number10-11
DOIs
StatePublished - May 28 2006

All Science Journal Classification (ASJC) codes

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