The parameterized hardness of the k-center problem in transportation networks
From MaRDI portal
(Redirected from Publication:5116483)
The parameterized hardness of the \(k\)-center problem in transportation networks (scientific article; zbMATH DE number 7238974)
The parameterized hardness of the \(k\)-center problem in transportation networks (scientific article; zbMATH DE number 7238974)
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)- Grundy Coloring and friends, half-graphs, bicliques
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- On the Parameterized Complexity of the Expected Coverage Problem
- On the parameterized complexity of the expected coverage problem
- Computing constrained shortest-paths at scale
- The k-centre problem for classes of cyclic words
- Travelling on graphs with small highway dimension
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- \(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension
- The parameterized hardness of the \(k\)-center problem in transportation networks
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)
