The parameterized hardness of the k-center problem in transportation networks
DOI10.4230/LIPICS.SWAT.2018.19zbMATH Open1477.68223OpenAlexW2963629213MaRDI QIDQ5116483FDOQ5116483
Authors: 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
Recommendations
- The parameterized hardness of the \(k\)-center problem in transportation networks
- \(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- Approximating \(k\)-center in planar graphs
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)
Cites Work
- Fundamentals of parameterized complexity
- The design of approximation algorithms
- Graph searching and a min-max theorem for tree-width
- Parameterized Algorithms
- Exact and approximation algorithms for clustering
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- VC-dimension and shortest path algorithms
- Title not available (Why is that?)
- Algorithms – ESA 2005
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- On the computational complexity of centers locating in a graph
- Approximating k-center in planar graphs
- Highway Dimension and Provably Efficient Shortest Path Algorithms
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lossy kernelization
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
Cited In (9)
- Grundy Coloring and friends, half-graphs, bicliques
- On the Parameterized Complexity of the Expected Coverage Problem
- On the parameterized complexity of the expected coverage problem
- The k-centre problem for classes of cyclic words
- 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
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- The parameterized hardness of the \(k\)-center problem in transportation networks
Uses Software
This page was built for publication: The parameterized hardness of the \(k\)-center problem in transportation networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116483)
