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 (15)
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
This page was built for publication: Parameterized approximation of dominating set problems
