On the Parameterized Complexity of Approximating Dominating Set
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Recommendations
- On the parameterized complexity of approximating dominating set
- Parameterized approximation of dominating set problems
- Algorithms – ESA 2004
- The constant inapproximability of the parameterized dominating set problem
- On the complexity of fixed parameter clique and dominating set
- Approximation algorithms for connected dominating sets
- Approximation algorithms for connected dominating sets
- Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
- Parameterized complexity of generalized domination problems
- Parameterized Complexity of Generalized Domination Problems
Cited in
(42)- The inapproximability of \(k\)-dominatingSet for parameterized \(\mathsf{{AC}^0}\) circuits
- A parameterized approximation scheme for generalized partial vertex cover
- On the parameterized complexity of approximating dominating set
- On sparse hitting sets: from fair vertex cover to highway dimension
- On the hardness of approximate and exact (bichromatic) maximum inner product
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Parameterized approximation of dominating set problems
- On the complexity of fixed parameter clique and dominating set
- Dual parameterization and parameterized approximability of subset graph problems
- Parameterized Complexity of Generalized Domination Problems
- Structural parameterizations of dominating set variants
- k-median/means with outliers revisited: a simple fpt approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Approximation and hardness of shift-bribery
- Search-space reduction via essential vertices
- Tight FPT approximation for socially fair clustering
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Approximation algorithms for connected dominating sets
- A note on hardness of computing recursive teaching dimension
- Approximation Algorithms and Hardness for Domination with Propagation
- On equivalence of parameterized inapproximability of \(k\)-median, \(k\)-max-coverage, and 2-CSP
- How to find a good explanation for clustering?
- Bicriteria approximation for minimum dilation graph augmentation
- scientific article; zbMATH DE number 2172821 (Why is no real title available?)
- Baby PIH: Parameterized inapproximability of min CSP
- A decidability result for the dominating set problem
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- The constant inapproximability of the parameterized dominating set problem
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- Applications of random algebraic constructions to hardness of approximation
- Parameterized inapproximability hypothesis under ETH
- Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
- FPT approximation of generalised hypertree width for bounded intersection hypergraphs
- On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
- Tight FPT approximation for constrained k-center and k-supplier
- Sidestepping barriers for dominating set in parameterized complexity
- On the complexity of Mixed Dominating Set
- Search-space reduction via essential vertices
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Recognizing when a preference system is close to admitting a master list
This page was built for publication: On the Parameterized Complexity of Approximating Dominating Set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215462)
