A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor

DOI10.1145/2629508zbMath1400.68158arXiv1302.3417OpenAlexW2444233166MaRDI QIDQ4962182

Dana Ron, Reut Levi

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.3417

zbMATH Keywords

planarityproperty testingminor-freepartition oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (11)

Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Testing outerplanarity of bounded degree graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local algorithms for sparse spanning graphs ⋮ On the characterization of 1-sided error strongly testable graph properties for 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 ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs

This page was built for publication: A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor