Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams

DOI10.1007/978-3-662-48350-3_72zbMath1422.68253arXiv1504.05476OpenAlexW1791386552MaRDI QIDQ3452847

Publication date: 19 November 2015

Published in: ACM Transactions on Algorithms, Algorithms - ESA 2015 (Search for Journal in Brave)

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

zbMATH Keywords

facility location Voronoi diagrams parameterized complexity packing problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80) Computer science (68-XX)

Related Items (42)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ Surprising Applications of Treewidth Bounds for Planar Graphs ⋮ Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ The parameterized hardness of the $k$-center problem in transportation networks ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Clique-based separators for geometric intersection graphs ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Constant-factor approximation algorithms for parity-constrained facility location and $k$-center ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ Algorithms for $k$-dispersion for points in convex position in the plane ⋮ Fixing improper colorings of graphs ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Unnamed Item ⋮ Subexponential-time algorithms for maximum independent set in $P_t$-free and broom-free graphs ⋮ Bundled Crossings Revisited ⋮ Fixed-parameter approximations for $k$-center problems in low highway dimension graphs ⋮ The complexity of dominating set in geometric intersection graphs ⋮ Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ A tight lower bound for planar Steiner orientation ⋮ Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs ⋮ The inverse Voronoi problem in graphs. I: Hardness ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of token swapping and its variants ⋮ Optimality program in segment and string graphs ⋮ On the minimum consistent subset problem ⋮ On Geometric Set Cover for Orthants ⋮ Parameterized inapproximability of independent set in $H$-free graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Structurally parameterized $d$-scattered set ⋮ Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking ⋮ The Dominating Set Problem in Geometric Intersection Graphs ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Faster 3-Coloring of Small-Diameter Graphs ⋮ Vertex cover at distance on $H$-free graphs

Cites Work

This page was built for publication: Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams