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 (22)

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 ⋮ 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

This page was built for publication: Better expanders and superconcentrators