Explicit construction of linear sized tolerant networks

N. Alon; F. R.K. Chung

doi:10.1016/0012-365X(88)90189-6

Explicit construction of linear sized tolerant networks

N. Alon, F. R.K. Chung

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

222 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 torerant linear arrays.

Original language	English (US)
Pages (from-to)	15-19
Number of pages	5
Journal	Discrete Mathematics
Volume	72
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(88)90189-6
State	Published - Dec 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(88)90189-6

Cite this

@article{482955cec3a445dfbe27a4b4483b8645,

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 torerant linear arrays.",

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

note = "Funding Information: * Research supported by the Israel Academy",

year = "1988",

month = dec,

doi = "10.1016/0012-365X(88)90189-6",

language = "English (US)",

volume = "72",

pages = "15--19",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Explicit construction of linear sized tolerant networks

AU - Alon, N.

AU - Chung, F. R.K.

N1 - Funding Information: * Research supported by the Israel Academy

PY - 1988/12

Y1 - 1988/12

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 torerant 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 torerant linear arrays.

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

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

U2 - 10.1016/0012-365X(88)90189-6

DO - 10.1016/0012-365X(88)90189-6

M3 - Article

AN - SCOPUS:38249028223

SN - 0012-365X

VL - 72

SP - 15

EP - 19

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

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