Tight approximation bounds for dominating set on graphs of bounded arboricity

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

zbMATH Keywords

dominating setapproximation algorithmsbounded arboricity

Mathematics Subject Classification ID

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