The parameterized hardness of the k-center problem in transportation networks
From MaRDI portal
Publication:5116483
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)
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
Cites work
- scientific article; zbMATH DE number 5734726 (Why is no real title available?)
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Algorithms – ESA 2005
- Approximating \(k\)-center in planar graphs
- Exact and approximation algorithms for clustering
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Fundamentals of parameterized complexity
- Graph searching and a min-max theorem for tree-width
- Highway dimension and provably efficient shortest path algorithms
- Highway dimension, shortest paths, and provably efficient algorithms
- Lossy kernelization
- On the computational complexity of centers locating in a graph
- Parameterized algorithms
- The design of approximation algorithms
- VC-dimension and shortest path algorithms
Cited in
(10)- The parameterized hardness of the \(k\)-center problem in transportation networks
- Computing constrained shortest-paths at scale
- On the Parameterized Complexity of the Expected Coverage Problem
- Grundy Coloring and friends, half-graphs, bicliques
- \(\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
- On the parameterized complexity of the expected coverage problem
- The k-centre problem for classes of cyclic words
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Travelling on graphs with small highway dimension
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)
