Approximating k-center in planar graphs

DOI10.1137/1.9781611973402.47zbMath1421.68215OpenAlexW4206688115MaRDI QIDQ5384008

Claire Mathieu, David Eisenstat, Philip N. Klein

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.47

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ The Euclidean \(k\)-supplier problem in \(I R^2\) ⋮ New Results on Directed Edge Dominating Set ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ Unnamed Item ⋮ A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks

This page was built for publication: Approximating k-center in planar graphs