\(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension

DOI10.1007/s10878-021-00792-4zbMath1504.90110OpenAlexW3082674212MaRDI QIDQ2084642

Johannes Blum

Publication date: 18 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00792-4

zbMATH Keywords

parameterized complexity\(k\)-centerhighway dimensionskeleton dimension

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

A parameterized approximation algorithm for the multiple allocation \(k\)-hub center

Cites Work

• Unnamed Item
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• The parameterized hardness of the \(k\)-center problem in transportation networks
• VC-Dimension and Shortest Path Algorithms
• Highway Dimension and Provably Efficient Shortest Path Algorithms
• 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
• Parameterized Algorithms
• Hierarchy of Transportation Network Parameters and Hardness Results

This page was built for publication: \(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension