Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs

DOI10.1007/S00453-018-0455-0zbMath1418.68241OpenAlexW2803914036WikidataQ129892606 ScholiaQ129892606MaRDI QIDQ666662

Andreas Emil Feldmann

Publication date: 11 March 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0455-0

zbMATH Keywords

\(k\)-\textsc{Center}highway dimensionparameterized approximation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (10)

The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ A parameterized approximation algorithm for the multiple allocation \(k\)-hub center ⋮ Unnamed Item ⋮ Graph burning and non-uniform \(k\)-centers for small treewidth ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Travelling on graphs with small highway dimension ⋮ \(\mathsf{W[1}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension] ⋮ Computing Constrained Shortest-Paths at Scale

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Easy and hard bottleneck location problems
• Some APX-completeness results for cubic graphs
• Exact and approximation algorithms for clustering
• Which problems have strongly exponential complexity?
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• 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
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• On the computational complexity of centers locating in a graph
• Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• The Parameterized Hardness of the k-Center Problem in Transportation Networks
• Search-Space Size in Contraction Hierarchies
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• On the complexity of \(k\)-SAT

This page was built for publication: Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs