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

被引：8

作者：

Dvorak, Zdenek ^{[1
]}

机构：

[1] Charles Univ Prague, Comp Sci Inst, Malostranske Namesti 25, CR-11800 Prague, Czech Republic

来源：

JOURNAL OF GRAPH THEORY | 2019年 / 91卷 / 02期

关键词：

approximation; dominating set; independent set; weak coloring number; APPROXIMATION ALGORITHMS; EXPANSION;

D O I：

10.1002/jgt.22426

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Dvorak [European J. Combin. 34 (2013), pp. 833-840] gave a bound on the minimum size of a distance r-dominating set in 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 a linear programming (LP)-based argument inspired by the work of Bansal and Umboh [Inform. Process. Lett. 122 (2017), pp. 21-24].

引用

页码：162 / 173

页数：12