An Expansion Tester for Bounded Degree Graphs

DOI10.1007/978-3-540-70575-8_43MaRDI QIDQ5900243zbMATH OpenOpenAlexFDO

Authors Satyen Kale, C. Seshadhri

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05)

Recommendations

• An expansion tester for bounded degree graphs
• Testing Expansion in Bounded-Degree Graphs
• Testing the expansion of a graph
• On testing expansion in bounded-degree graphs
• scientific article; zbMATH DE number 1559556

Cited in

(18)

• On testable properties in bounded degree graphs
• Testing cluster structure of graphs
• Testing small set expansion in general graphs
• Parameter testing in bounded degree graphs of subexponential growth
• On testing expansion in bounded-degree graphs
• Introduction to testing graph properties
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• scientific article; zbMATH DE number 1559556 (Why is no real title available?)
• scientific article; zbMATH DE number 1775414 (Why is no real title available?)
• Testing Expansion in Bounded-Degree Graphs
• Introduction to testing graph properties
• Testing outerplanarity of bounded degree graphs
• Tight bounds for the cover time of multiple random walks
• An expansion tester for bounded degree graphs
• Testing Eulerianity and connectivity in directed sparse graphs
• Approximating Dasgupta cost in sublinear time from a few random seeds
• Every minor-closed property of sparse graphs is testable
• Testing the expansion of a graph

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

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