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

DOI10.4230/LIPIcs.ESA.2018.65OpenAlexW2883490064MaRDI QIDQ5009632

Michał Pilipczuk, Andreas Wiese, Erik Jan van Leeuwen

Publication date: 4 August 2021

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

zbMATH Keywords

planar graphsVoronoi diagramQPTAS

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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