Article ID Journal Published Year Pages File Type
4950892 Information Processing Letters 2017 4 Pages PDF
Abstract
We consider the minimum dominating set problem on graphs with bounded arboricity. For graphs with arboricity a, we give an LP rounding algorithm that achieves an approximation factor of 3a and we complement this with a matching (up to constants) hardness of approximation result.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Tight approximation bounds for dominating set on graphs of bounded arboricity
Authors
, ,