Parameterized approximation of dominating set problems

DOI10.1016/j.ipl.2008.09.017zbMath1191.68862WikidataQ57359917 ScholiaQ57359917MaRDI QIDQ975529

Michael R. Fellows, Rodney G. Downey, Frances A. Rosamond, Catherine McCartin

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

zbMATH Keywords

approximation algorithms; parameterized complexity; FPT approximation

Mathematics Subject Classification ID

68W25: Approximation algorithms

Related Items

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, 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