Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

DOI10.1137/070681831MaRDI QIDQ3654386zbMATH OpenOpenAlexFDO

Authors Asaf Shapira, Christian Sohler, 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

zbMATH Keywords

approximation algorithmsbounded-degree graphshereditary graph propertiesnonexpanding graphsplanar graphsproperty testingrandomized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• On testing expansion in bounded-degree graphs
• Testing Expansion in Bounded-Degree Graphs
• Property testing in bounded degree graphs
• scientific article; zbMATH DE number 1559556
• On testable properties in bounded degree graphs
• An expansion tester for bounded degree graphs
• An Expansion Tester for Bounded Degree Graphs
• Testability and repair of hereditary hypergraph properties
• A survey of hereditary properties of graphs
• Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Cited in

(28)

• Comparing the strength of query types in property testing: the case of \(k\)-colorability
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• On testable properties in bounded degree graphs
• Constructing near spanning trees with few local inspections
• Parameter testing in bounded degree graphs of subexponential growth
• An efficient partitioning oracle for bounded-treewidth graphs
• Inflatable graph properties and natural property tests
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• scientific article; zbMATH DE number 1554934 (Why is no real title available?)
• Testing Expansion in Bounded-Degree Graphs
• Sublinear-time Algorithms
• Sublinear graph approximation algorithms
• Testing Euclidean Spanners
• Testing hereditary properties of sequences
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• The subgraph testing model
• Planar graphs: random walks and bipartiteness testing
• Testing subdivision-freeness: property testing meets structural graph theory
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Property testing in bounded degree graphs
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Faster Property Testers in a Variation of the Bounded Degree Model
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• Towards the Erdős-Gallai cycle decomposition conjecture
• Intervention efficient algorithms for approximate learning of causal graphs
• Pliability and approximating Max-CSPs
• Testing depth first search numbering
• Every minor-closed property of sparse graphs is testable

This page was built for publication: Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

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