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:3387757
DOI10.1137/19M1245463zbMath1506.68075arXiv1805.08187OpenAlexW3114178996MaRDI QIDQ3387757
C. Seshadhri, Akash Kumar, Andrew M. Stolman
Publication date: 13 January 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.08187
Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Randomized algorithms (68W20) Random walks on graphs (05C81)
Related Items
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of 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
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
- Über eine Eigenschaft der ebenen Komplexe
- 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
- 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
- Random walks and forbidden minors II
- Introduction to Property Testing
- An Expansion Tester for Bounded Degree Graphs
- Property testing in bounded degree graphs
