Better expanders and superconcentrators

DOI10.1016/0196-6774(87)90014-9zbMath0641.68102OpenAlexW2058640826MaRDI QIDQ3782808

Noga Alon, Zvi Galil, Vitali D. Milman

Publication date: 1987

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(87)90014-9

zbMATH Keywords

expandersRamanujan graphssuperconcentrators

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Cutoff for random lifts of weighted graphs, On the relationship between the diameter and the size of a boundary of a directed graph, Multi-processor scheduling and expanders, On using deterministic functions to reduce randomness in probabilistic algorithms, Expanders obtained from affine transformations, On embedding graphs in trees, Eigenvalues and expanders, A geometric condition for incidence-matrix nullvectors, Expanders and Diffusers, Generating sets for the multiplicative groups of algebras over finite fields and expander graphs, Pseudorandom generators for combinatorial checkerboards, Matching nuts and bolts faster, Construction of expanders and superconcentrators using Kolmogorov complexity, Edge intersection graphs of systems of paths on a grid with a bounded number of bends, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Minimal selectors and fault tolerant networks, Natural bounded concentrators, Effect of connectivity in an associative memory model, \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators, Laplacian matrices of graphs: A survey, Diameters and Eigenvalues