The Parameterized Hardness of the k-Center Problem in Transportation Networks

DOI10.4230/LIPIcs.SWAT.2018.19zbMath1477.68223OpenAlexW2963629213MaRDI QIDQ5116483

Andreas Emil Feldmann, Dániel Marx

Publication date: 25 August 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8845/pdf/LIPIcs-SWAT-2018-19.pdf

zbMATH Keywords

planar graphstreewidthdoubling dimensionparameterized complexity\(k\)-centerhighway dimension

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (8)

On the Parameterized Complexity of the Expected Coverage Problem ⋮ On the parameterized complexity of the expected coverage problem ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ The k-centre problem for classes of cyclic words ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Travelling on graphs with small highway dimension ⋮ Computing Constrained Shortest-Paths at Scale

Uses Software

• DIMACS

Cites Work

• Fundamentals of parameterized complexity
• Graph searching and a min-max theorem for tree-width
• Exact and approximation algorithms for clustering
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• The Design of Approximation Algorithms
• VC-Dimension and Shortest Path Algorithms
• Highway Dimension and Provably Efficient Shortest Path Algorithms
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• On the computational complexity of centers locating in a graph
• Lossy kernelization
• Approximating k-center in planar graphs
• Algorithms – ESA 2005
• Parameterized Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Parameterized Hardness of the k-Center Problem in Transportation Networks