Better expanders and superconcentrators

N. Alon; Z. Galil; V. D. Milman

doi:10.1016/0196-6774(87)90014-9

Better expanders and superconcentrators

N. Alon, Z. Galil, V. D. Milman

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

35 Scopus citations

Abstract

Explicit construction of families of linear expanders and superconcentrators is relevant to theoretical computer science in several ways. Here we construct better expanders than those previously known and use them to construct explicitly n-superconcentrators with ≈ 122.74n edges; much less than the previous most economical construction.

Original language	English (US)
Pages (from-to)	337-347
Number of pages	11
Journal	Journal of Algorithms
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/0196-6774(87)90014-9
State	Published - Sep 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(87)90014-9

Cite this

@article{f6605606c22f47f399e43d7ef781488c,

title = "Better expanders and superconcentrators",

abstract = "Explicit construction of families of linear expanders and superconcentrators is relevant to theoretical computer science in several ways. Here we construct better expanders than those previously known and use them to construct explicitly n-superconcentrators with ≈ 122.74n edges; much less than the previous most economical construction.",

author = "N. Alon and Z. Galil and Milman, {V. D.}",

note = "Funding Information: *Research supported in part by the Weizmann Fellowship for Scientific Research and by NSF under Contract DMS8406100. +Research supported in part by NSF Grants MCS-8303139 and DCR-8511713.",

year = "1987",

month = sep,

doi = "10.1016/0196-6774(87)90014-9",

language = "English (US)",

volume = "8",

pages = "337--347",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Better expanders and superconcentrators

AU - Alon, N.

AU - Galil, Z.

AU - Milman, V. D.

N1 - Funding Information: *Research supported in part by the Weizmann Fellowship for Scientific Research and by NSF under Contract DMS8406100. +Research supported in part by NSF Grants MCS-8303139 and DCR-8511713.

PY - 1987/9

Y1 - 1987/9

N2 - Explicit construction of families of linear expanders and superconcentrators is relevant to theoretical computer science in several ways. Here we construct better expanders than those previously known and use them to construct explicitly n-superconcentrators with ≈ 122.74n edges; much less than the previous most economical construction.

AB - Explicit construction of families of linear expanders and superconcentrators is relevant to theoretical computer science in several ways. Here we construct better expanders than those previously known and use them to construct explicitly n-superconcentrators with ≈ 122.74n edges; much less than the previous most economical construction.

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

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

U2 - 10.1016/0196-6774(87)90014-9

DO - 10.1016/0196-6774(87)90014-9

M3 - Article

AN - SCOPUS:38249033599

SN - 0196-6774

VL - 8

SP - 337

EP - 347

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 3

ER -

Better expanders and superconcentrators

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this