Better expanders and superconcentrators

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

Research output: Contribution to journalArticle

33 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 languageEnglish (US)
Pages (from-to)337-347
Number of pages11
JournalJournal of Algorithms
Volume8
Issue number3
DOIs
StatePublished - Sep 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Better expanders and superconcentrators'. Together they form a unique fingerprint.

  • Cite this