On distance r-dominating and 2r-independent sets in sparse graphs

Zden\v{e}k Dvo\v{r}\'ak

arxiv: 1710.10010 · v1 · pith:SI75QE7Anew · submitted 2017-10-27 · 🧮 math.CO · cs.DM

On distance r-dominating and 2r-independent sets in sparse graphs

Zden\v{e}k Dvo\v{r}\'ak This is my paper

classification 🧮 math.CO cs.DM

keywords distancegraphssizealgorithmapproximationargumentbansalbound

0 comments

read the original abstract

Dvorak (2013) gave a bound on the minimum size of a distance r dominating set in the terms of the maximum size of a distance 2r 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 an LP-based argument inspired by the work of Bansal and Umboh (2017).

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Domination above r-independence: does sparseness help?
cs.DS 2019-06 conditional novelty 6.0

Dominating Set above r-independence is paraNP-complete for r=2 even on apex and bounded-degree graphs, W[2]-hard but FPT on nowhere dense graphs for r=3 with linear kernel on bounded expansion, and equivalent to stand...