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

DOI10.1145/2629508zbMath1400.68158arXiv1302.3417MaRDI 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

planarity; property testing; minor-free; partition oracle

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C83: Graph minors

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W20: Randomized algorithms