Parameterized approximation of dominating set problems
From MaRDI portal
Publication:975529
DOI10.1016/j.ipl.2008.09.017zbMath1191.68862WikidataQ57359917 ScholiaQ57359917MaRDI QIDQ975529
Catherine McCartin, Frances A. Rosamond, Michael R. Fellows, Rodney G. Downey
Publication date: 9 June 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2008.09.017
68W25: Approximation algorithms
Related Items
The Constant Inapproximability of the Parameterized Dominating Set Problem, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Perfect domination and small cycles, Exponential approximation schemata for some network design problems, Confronting intractability via parameters, Time-approximation trade-offs for inapproximable problems, Parameterized approximation via fidelity preserving transformations, On subexponential and FPT-time inapproximability, New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set, Parameterized and exact algorithms for class domination coloring, A Basic Parameterized Complexity Primer, Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems, Parameterized and Exact Algorithms for Class Domination Coloring, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries
Cites Work
- Unnamed Item
- Unnamed Item
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- The Parameterized Complexity of Counting Problems
- Parameterized and Exact Computation
- Parameterized Approximability of the Disjoint Cycle Problem
