On the Parameterized Complexity of Approximating Dominating Set
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Approximation algorithms (68W25)
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
(46)- Structural parameterizations of dominating set variants
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Approximation and hardness of shift-bribery
- The inapproximability of \(k\)-dominatingSet for parameterized \(\mathsf{{AC}^0}\) circuits
- On the complexity of Mixed Dominating Set
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Tight FPT approximation for constrained k-center and k-supplier
- Dual parameterization and parameterized approximability of subset graph problems
- A decidability result for the dominating set problem
- Approximation algorithms for connected dominating sets
- The constant inapproximability of the parameterized dominating set problem
- scientific article; zbMATH DE number 2172821 (Why is no real title available?)
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- On the hardness of approximate and exact (bichromatic) maximum inner product
- On the parameterized complexity of approximating dominating set
- Parameterized Complexity of Generalized Domination Problems
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Approximation Algorithms and Hardness for Domination with Propagation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- A note on hardness of computing recursive teaching dimension
- Recognizing when a preference system is close to admitting a master list
- How to find a good explanation for clustering?
- A parameterized approximation scheme for generalized partial vertex cover
- Tight FPT approximation for socially fair clustering
- k-median/means with outliers revisited: a simple fpt approximation
- Search-space reduction via essential vertices
- Baby PIH: Parameterized inapproximability of min CSP
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- 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
- FPT approximation of generalised hypertree width for bounded intersection hypergraphs
- On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
- Sidestepping barriers for dominating set in parameterized complexity
- On sparse hitting sets: from fair vertex cover to highway dimension
- Search-space reduction via essential vertices
- On the complexity of fixed parameter clique and dominating set
- Bicriteria approximation for minimum dilation graph augmentation
- On equivalence of parameterized inapproximability of \(k\)-median, \(k\)-max-coverage, and 2-CSP
- Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
- On average baby PIH and its applications
- FPT approximation of generalised hypertree width for bounded intersection hypergraphs
- From Chinese postman to salesman and beyond. II: Inapproximability and parameterized complexity
- Fine-grained classification of detecting dominating patterns
- Parameterized approximation of dominating set problems
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)
