scientific article; zbMATH DE number 7278055
From MaRDI portal
Publication:5136270
Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Approximation algorithms (68W25)
Recommendations
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- A technique for obtaining true approximations for \(k\)-center with covering constraints
- A technique for obtaining true approximations for k-center with covering constraints
- scientific article; zbMATH DE number 2038758
- The approximability of the \(p\)-hub center problem with parameterized triangle inequality
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Approximating k-center in planar graphs
- Generalized p-center problems: Complexity results and approximation algorithms
- \(k\)-centerpoints conjectures for pointsets in \(\mathbb{R}^d\)
- Approximating the restricted 1-center in graphs
Cites work
- R -Domination in Graphs
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Algorithms – ESA 2005
- AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
- Approximating k-center in planar graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Exact and approximation algorithms for clustering
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Faster algorithms on branch and clique decompositions
- Fault tolerant \(K\)-center problems
- 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
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamentals of parameterized complexity
- Hardness of r-dominating set on graphs of diameter (r + 1)
- scientific article; zbMATH DE number 1696534 (Why is no real title available?)
- scientific article; zbMATH DE number 6474898 (Why is no real title available?)
- scientific article; zbMATH DE number 2086260 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the complexity of k-SAT
- Optimal dynamic program for r-domination problems over tree decompositions
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Parameterized algorithms
- Parameterized Approximation Schemes Using Graph Widths
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Parametrized complexity theory.
- Practical algorithms on partial k-trees with an application to domination-like problems
- The k-hop connected dominating set problem: hardness and polyhedra
- The Capacitated K-Center Problem
- Tree-depth, subgraph coloring and homomorphism bounds
- Treewidth. Computations and approximations
- Treewidth: Characterizations, Applications, and Computations
- Upper bounds to the clique width of graphs
- Which problems have strongly exponential complexity?
Cited in
(12)- \(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension
- A technique for obtaining true approximations for \(k\)-center with covering constraints
- Tight FPT approximation for constrained k-center and k-supplier
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Approximating the Restricted 1-Center in Graphs
- scientific article; zbMATH DE number 2038758 (Why is no real title available?)
- scientific article; zbMATH DE number 6820208 (Why is no real title available?)
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Travelling on graphs with small highway dimension
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136270)
