Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
From MaRDI portal
Publication:3654386
DOI10.1137/070681831zbMath1191.68850OpenAlexW2052194338MaRDI QIDQ3654386
Christian Sohler, Asaf Shapira, Artur Czumaj
Publication date: 6 January 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/37021/1/WRAP_Czumaj%2C_GetPDFServlet3.pdf
planar graphsapproximation algorithmsrandomized algorithmsproperty testingbounded-degree graphshereditary graph propertiesnonexpanding graphs
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (19)
Faster Property Testers in a Variation of the Bounded Degree Model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Comparing the strength of query types in property testing: the case of \(k\)-colorability ⋮ Constructing near spanning trees with few local inspections ⋮ Unnamed Item ⋮ Testing Euclidean Spanners ⋮ Testing Expansion in Bounded-Degree Graphs ⋮ Every minor-closed property of sparse graphs is testable ⋮ Sublinear-time Algorithms ⋮ Sublinear Graph Approximation Algorithms ⋮ Unnamed Item ⋮ Parameter testing in bounded degree graphs of subexponential growth ⋮ On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs ⋮ An Efficient Partitioning Oracle for Bounded-Treewidth 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 ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Unnamed Item
This page was built for publication: Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
