An Expansion Tester for Bounded Degree Graphs
From MaRDI portal
Publication:5900243
DOI10.1007/978-3-540-70575-8_43zbMath1153.68466MaRDI QIDQ5900243
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
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Introduction to Testing Graph Properties, Tight bounds for the cover time of multiple random walks, Testing Eulerianity and connectivity in directed sparse graphs, Every minor-closed property of sparse graphs is testable, Testing the expansion of a graph, On Testing Expansion in Bounded-Degree Graphs, Introduction to Testing Graph Properties