An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity

DOI10.1007/978-3-030-92702-8_3OpenAlexW4206802467MaRDI QIDQ2085734

Yanyan Li

Publication date: 19 October 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92702-8_3

zbMATH Keywords

dominating setapproximation algorithmsbounded arboricity

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Approximation algorithms for NP-complete problems on planar graphs
• Analytical approach to parallel repetition

This page was built for publication: An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity