Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs

DOI10.1007/s00453-019-00670-wzbMath1433.68307OpenAlexW3000473895MaRDI QIDQ1987245

Erik Jan van Leeuwen, Andreas Wiese, Michał Pilipczuk

Publication date: 14 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9528/

zbMATH Keywords

planar graphsapproximation schemesgeometric set coverindependent set of objects

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

Minimum constellation covers: hardness, approximability and polynomial cases

Cites Work

• Finding small simple cycle separators for 2-connected planar graphs
• Call routing and the ratcatcher
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
• A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices