An Expansion Tester for Bounded Degree Graphs

DOI10.1137/100802980zbMath1235.68084OpenAlexW2087439135MaRDI QIDQ5894298

C. Seshadhri, Satyen Kale

Publication date: 18 October 2011

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

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

zbMATH Keywords

random walkssublinear algorithmsgraph expansion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

Well-mixing vertices and almost expanders ⋮ Unnamed Item ⋮ Zero-Knowledge Proofs of Proximity ⋮ Unnamed Item ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Dynamic complexity of expansion

This page was built for publication: An Expansion Tester for Bounded Degree Graphs