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

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

zbMATH Keywords

property testingbounded degree graphsminor-free graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
• 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
• Title not available (Why is that?)
• 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)