Parameterized approximation of dominating set problems
From MaRDI portal
Publication:975529
DOI10.1016/j.ipl.2008.09.017zbMath1191.68862OpenAlexW2030965968WikidataQ57359917 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
Related Items
A Basic Parameterized Complexity Primer, Parameterized and exact algorithms for class domination coloring, Time-approximation trade-offs for inapproximable problems, Exponential approximation schemata for some network design problems, Parameterized approximation via fidelity preserving transformations, Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Perfect domination and small cycles, Parameterized and Exact Algorithms for Class Domination Coloring, Confronting intractability via parameters, The Constant Inapproximability of the Parameterized Dominating Set Problem, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries, On subexponential and FPT-time inapproximability, New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
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
