Structural parameters, tight bounds, and approximation for \((k, r)\)-center
From MaRDI portal
Publication:2422740
DOI10.1016/j.dam.2018.11.002zbMath1414.05102arXiv1704.08868OpenAlexW2964301480MaRDI QIDQ2422740
Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
Publication date: 20 June 2019
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.08868
Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ Parameterized (Approximate) Defective Coloring ⋮ A parameterized approximation algorithm for the multiple allocation \(k\)-hub center ⋮ Unnamed Item ⋮ Graph burning and non-uniform \(k\)-centers for small treewidth ⋮ Unnamed Item ⋮ Structurally parameterized \(d\)-scattered set
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The \(k\)-hop connected dominating set problem: hardness and polyhedra
- Fundamentals of parameterized complexity
- Sparsity. Graphs, structures, and algorithms
- The fault-tolerant capacitated \(K\)-center problem
- Clustering to minimize the maximum intercluster distance
- Treewidth. Computations and approximations
- Fault tolerant \(K\)-center problems
- Exact and approximation algorithms for clustering
- Which problems have strongly exponential complexity?
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Parameterized edge Hamiltonicity
- Scheduling of pipelined operator graphs
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Parametrized complexity theory.
- Tree-depth, subgraph coloring and homomorphism bounds
- Hardness of r-dominating set on Graphs of Diameter (r + 1)
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Parameterized Power Vertex Cover
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Treewidth: Characterizations, Applications, and Computations
- Fourier meets M\"{o}bius: fast subset convolution
- Faster Algorithms on Branch and Clique Decompositions
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- R -Domination in Graphs
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
- How to Allocate Network Centers
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- The Capacitated K-Center Problem
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Optimal dynamic program for r-domination problems over tree decompositions
- Parameterized Approximation Schemes Using Graph Widths
- Approximating k-center in planar graphs
- Algorithms – ESA 2005
- Parameterized Algorithms
- Parameterized approximation algorithms for some location problems in graphs
- On the complexity of \(k\)-SAT
