Random Walks and Forbidden Minors I: An n^{1/2+o(1)}-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
DOI10.1137/19M1245463OpenAlexW3114178996MaRDI QIDQ6139828FDOQ6139828
Authors: A. Kumar, C. Seshadhri, Andrew M. Stolman 
Publication date: 19 December 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1245463
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Graph minors (05C83)
Cites Work
- Graph theory
- Graph minors. XX: Wagner's conjecture
- Efficient Planarity Testing
- Property testing in bounded degree graphs
- The disjoint paths problem in quadratic time
- Graph minor theory
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- A sublinear bipartiteness tester for bounded degree graphs
- Testing the expansion of a graph
- On testing expansion in bounded-degree graphs
- An efficient partitioning oracle for bounded-treewidth graphs
- Testing Expansion in Bounded-Degree Graphs
- Testing outerplanarity of bounded degree graphs
- Local Graph Partitions for Approximation and Testing
- An expansion tester for bounded degree graphs
- Every minor-closed property of sparse graphs is testable
- Subexponential algorithms for unique games and related problems
- A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
- Noise tolerance of expanders and sublinear expansion reconstruction
- Introduction to Property Testing
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Testing cluster structure of graphs
- Finding cycles and trees in sublinear time
- A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- Title not available (Why is that?)
This page was built for publication: Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139828)
