Publication at Faculty of Mathematics and Physics |
2019
Abstract
Dvořák [European J. Combin. 34 (2013), pp. 833-840] gave a bound on the minimum size of a distance -dominating set in terms of the maximum size of a distance -independent set and generalized coloring numbers, thus obtaining a constant-factor approximation algorithm for the parameters in any class of graphs with bounded expansion.
We improve and clarify this dependence using a linear programming (LP)-based argument inspired by the work of Bansal and Umboh [Inform. Process.
Lett. 122 (2017), pp. 21-24].