Testing the expansion of a graph

DOI10.1016/j.ic.2009.09.002zbMath1194.68173OpenAlexW2115464252MaRDI QIDQ963057

Asaf Nachmias, Asaf Shapira

Publication date: 8 April 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2009.09.002

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Spanders: distributed spanning expanders, Global information from local observations of the noisy voter model on a graph, Orion: zero knowledge proof with linear prover time, Introduction to Testing Graph Properties, Testing Eulerianity and connectivity in directed sparse graphs, Zero-Knowledge Proofs of Proximity, Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks, Every minor-closed property of sparse graphs is testable, Testing the expansion of a graph, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs, Quantum Property Testing for Bounded-Degree Graphs, Introduction to Testing Graph Properties, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing the expansion of a graph
• Eigenvalues and expanders
• A sublinear bipartiteness tester for bounded degree graphs
• On Testing Expansion in Bounded-Degree Graphs
• Expander graphs and their applications
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• An Expansion Tester for Bounded Degree Graphs
• Property testing in bounded degree graphs