Testing the expansion of a graph

DOI10.1016/J.IC.2009.09.002MaRDI QIDQ963057zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Testing Expansion in Bounded-Degree Graphs
• An Expansion Tester for Bounded Degree Graphs
• An expansion tester for bounded degree graphs
• On testing expansion in bounded-degree graphs
• Testing small set expansion in general graphs

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 5605086 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• A sublinear bipartiteness tester for bounded degree graphs
• An Expansion Tester for Bounded Degree Graphs
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Eigenvalues and expanders
• Expander graphs and their applications
• On testable properties in bounded degree graphs
• On testing expansion in bounded-degree graphs
• Property testing in bounded degree graphs
• Testing the expansion of a graph

Cited in

(21)

• Spanders: distributed spanning expanders
• An expansion tester for bounded degree graphs
• Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
• Global information from local observations of the noisy voter model on a graph
• Testing the expansion of a graph
• Zero-knowledge proofs of proximity
• Testing small set expansion in general graphs
• Testing cluster structure of graphs
• Testing Eulerianity and connectivity in directed sparse graphs
• A test for expandability
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• Orion: zero knowledge proof with linear prover time
• Introduction to testing graph properties
• 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
• Testing Expansion in Bounded-Degree Graphs
• An Expansion Tester for Bounded Degree Graphs
• On testing expansion in bounded-degree graphs
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Every minor-closed property of sparse graphs is testable
• Quantum property testing for bounded-degree graphs

This page was built for publication: Testing the expansion of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963057)