Random Walks and Forbidden Minors II: A \mathrm{poly}(d\varepsilon^{-1})-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs

DOI10.1137/20M1312824MaRDI QIDQ5890147zbMATH OpenOpenAlexFDO

Authors A. Kumar, C. Seshadhri, Andrew M. Stolman

Publication date 28 April 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20m1312824

zbMATH Keywords

graph minorsproperty testingsublinear algorithms

Mathematics Subject Classification ID

Graph minors (05C83) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Random walks and forbidden minors II
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• Every minor-closed property of sparse graphs is testable
• scientific article; zbMATH DE number 1559556
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error

Cites work

• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• A Separator Theorem for Nonplanar Graphs
• A sublinear bipartiteness tester for bounded degree graphs
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• An efficient partitioning oracle for bounded-treewidth graphs
• Concentration of Measure for the Analysis of Randomized Algorithms
• Efficient Planarity Testing
• Every property of hyperfinite graphs is testable
• Finding cycles and trees in sublinear time
• Graph minors. XII: Distance on a surface
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Graph theory
• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• Introduction to Property Testing
• Local Graph Partitions for Approximation and Testing
• Noise tolerance of expanders and sublinear expansion reconstruction
• Property testing in 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
• Testing outerplanarity of bounded degree graphs
• The disjoint paths problem in quadratic time
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(4)

• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• Random walks and forbidden minors II
• Every minor-closed property of sparse graphs is testable

This page was built for publication: Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs

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