Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
From MaRDI portal
Publication:6139828
DOI10.1137/19m1245463OpenAlexW3114178996MaRDI QIDQ6139828
Akash 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) Graph minors (05C83) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- Testing outerplanarity of bounded degree graphs
- Graph minors. XX: Wagner's conjecture
- Every minor-closed property of sparse graphs is testable
- Testing the expansion of a graph
- A sublinear bipartiteness tester for bounded degree graphs
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Noise Tolerance of Expanders and Sublinear Expansion Reconstruction
- Finding cycles and trees in sublinear time
- Testing Cluster Structure of Graphs
- An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- On Testing Expansion in Bounded-Degree Graphs
- Subexponential Algorithms for Unique Games and Related Problems
- Graph minor theory
- 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 Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Efficient Planarity Testing
- Testing Expansion in Bounded-Degree Graphs
- A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
- Local Graph Partitions for Approximation and Testing
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Introduction to Property Testing
- An Expansion Tester for Bounded Degree Graphs
- Property testing in bounded degree graphs
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
