Explicit Construction of Linear Sized Tolerant Networks

N. Alon; F. R.K. Chung

doi:10.1016/S0167-5060(08)70766-0

Explicit Construction of Linear Sized Tolerant Networks

N. Alon, F. R.K. Chung

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

29 Scopus citations

Abstract

For every ɛ0 and every integer m0, we construct explicitly graphs with O(mɛ vertices and maximum degree O(1ɛ²), 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 language	English (US)
Pages (from-to)	15-19
Number of pages	5
Journal	Annals of Discrete Mathematics
Volume	38
Issue number	C
DOIs	https://doi.org/10.1016/S0167-5060(08)70766-0
State	Published - Jan 1 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0167-5060(08)70766-0

Cite this

@article{76c5d5925fa74f059e25fc7e6da9b731,

title = "Explicit Construction of Linear Sized Tolerant Networks",

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

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

note = "Funding Information: Research supported in part by Allon Fellowship and by the fund for basic research administered by the Israel Academy of Sciences.",

year = "1988",

month = jan,

day = "1",

doi = "10.1016/S0167-5060(08)70766-0",

language = "English (US)",

volume = "38",

pages = "15--19",

journal = "Annals of Discrete Mathematics",

issn = "0167-5060",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - Explicit Construction of Linear Sized Tolerant Networks

AU - Alon, N.

AU - Chung, F. R.K.

N1 - Funding Information: Research supported in part by Allon Fellowship and by the fund for basic research administered by the Israel Academy of Sciences.

PY - 1988/1/1

Y1 - 1988/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=77957074439&partnerID=8YFLogxK

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

U2 - 10.1016/S0167-5060(08)70766-0

DO - 10.1016/S0167-5060(08)70766-0

M3 - Article

AN - SCOPUS:77957074439

SN - 0167-5060

VL - 38

SP - 15

EP - 19

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

IS - C

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