Explicit construction of linear sized tolerant networks

N. Alon; F. R.K. Chung

doi:10.1016/j.disc.2006.03.025

Explicit construction of linear sized tolerant networks

N. Alon, F. R.K. Chung

Research output: Contribution to journal › Article › peer-review

6 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}²), 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 language	English (US)
Pages (from-to)	1068-1071
Number of pages	4
Journal	Discrete Mathematics
Volume	306
Issue number	10-11
DOIs	https://doi.org/10.1016/j.disc.2006.03.025
State	Published - May 28 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2006.03.025

Cite this

@article{ae9a27a2099a4529896fe4801aea02c7,

title = "Explicit construction of linear sized tolerant networks",

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.",

author = "N. Alon and Chung, \{F. R.K.\}",

year = "2006",

month = may,

day = "28",

doi = "10.1016/j.disc.2006.03.025",

language = "English (US)",

volume = "306",

pages = "1068--1071",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "10-11",

}

TY - JOUR

T1 - Explicit construction of linear sized tolerant networks

AU - Alon, N.

AU - Chung, F. R.K.

PY - 2006/5/28

Y1 - 2006/5/28

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/33744515042

UR - https://www.scopus.com/inward/citedby.url?scp=33744515042&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2006.03.025

DO - 10.1016/j.disc.2006.03.025

M3 - Article

AN - SCOPUS:33744515042

SN - 0012-365X

VL - 306

SP - 1068

EP - 1071

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10-11

ER -

Explicit construction of linear sized tolerant networks

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this