Tight approximation bounds for dominating set on graphs of bounded arboricity
From MaRDI portal
Publication:1675919
DOI10.1016/j.ipl.2017.01.011zbMath1422.68291OpenAlexW2589200750MaRDI QIDQ1675919
Nikhil Bansal, Seeun William Umboh
Publication date: 3 November 2017
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2017.01.011
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (7)
Greedy domination on biclique-free graphs ⋮ A Constructive Arboricity Approximation Scheme ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity ⋮ Local planar domination revisited ⋮ Constant round distributed domination on graph classes with bounded expansion
Cites Work
- Approximation hardness of dominating set problems in bounded degree graphs
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
- On the power of unique 2-prover 1-round games
- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- Analytical approach to parallel repetition
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
This page was built for publication: Tight approximation bounds for dominating set on graphs of bounded arboricity