Limitations on Explicit Constructions of Expanding Graphs

DOI10.1137/0213011zbMath0537.68068OpenAlexW1966779504MaRDI QIDQ3323289

Maria M. Klawe

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213011

zbMATH Keywords

networkexpanding graphspseudo-random number generatorssuperconcentrator

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Other designs, configurations (05B30) Connectivity (05C40)

Related Items (14)

On the relationship between the diameter and the size of a boundary of a directed graph ⋮ On the diameter and bisector size of Cayley graphs ⋮ A Novel Compressed Sensing Scheme for Photoacoustic Tomography ⋮ Expanders obtained from affine transformations ⋮ Finite fields and Ramanujan graphs ⋮ A separator theorem for one-dimensional graphs under linear mapping ⋮ Expansion in SL\(_2(\mathbb R)\) and monotone expanders ⋮ Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time ⋮ Expanders and Diffusers ⋮ On constructing expander families of G-graphs ⋮ Symmetric groups and expander graphs. ⋮ Quantum Chaos on Random Cayley Graphs of SL 2[Z/pZ] ⋮ Natural bounded concentrators ⋮ Spectral estimates for abelian Cayley graphs

This page was built for publication: Limitations on Explicit Constructions of Expanding Graphs