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
相关论文
共 22 条
  • [1] Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs
    Kreutzer, Stephan
    Rabinovich, Roman
    Siebertz, Sebastian
    Weberstaedt, Grischa
    34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017), 2017, 66
  • [2] On the Number of -Dominating Independent Sets in Planar Graphs
    Taletskii D.S.
    Journal of Applied and Industrial Mathematics, 2024, 18 (01) : 167 - 178
  • [3] Kernelization and approximation of distance-r independent sets on nowhere dense graphs
    Pilipczuk, Michal
    Siebertz, Sebastian
    EUROPEAN JOURNAL OF COMBINATORICS, 2021, 94
  • [4] Efficient enumeration of dominating sets for sparse graphs
    Kurita, Kazuhiro
    Wasa, Kunihiro
    Arimura, Hiroki
    Uno, Takeaki
    DISCRETE APPLIED MATHEMATICS, 2021, 303 : 283 - 295
  • [5] INDEPENDENT SET DOMINATING SETS IN BIPARTITE GRAPHS
    Zelinka, Bohdan
    OPUSCULA MATHEMATICA, 2005, 25 (02) : 345 - 349
  • [6] Independent point-set dominating sets in graphs
    Gupta, Purnima
    Goyal, Alka
    Jain, Ranjana
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (01) : 229 - 241
  • [7] Minimum connected dominating sets and maximal independent sets in unit disk graphs
    Wu, WL
    Du, HW
    Jia, XH
    Li, YS
    Huang, SCH
    THEORETICAL COMPUTER SCIENCE, 2006, 352 (1-3) : 1 - 7
  • [8] Graphs such that All Minimum Dominating Sets Intersect All Maximally Independent Sets
    Johnson, P. D., Jr.
    Prier, D. R.
    UTILITAS MATHEMATICA, 2012, 89 : 211 - 224
  • [9] On Proper 2-Dominating Sets in Graphs
    Bednarz, Pawel
    Pirga, Mateusz
    SYMMETRY-BASEL, 2024, 16 (03):
  • [10] Efficient Self-Stabilizing Algorithm for Independent Strong Dominating Sets in Arbitrary Graphs
    Neggazi, Brahim
    Guellati, Nabil
    Haddad, Mohammed
    Kheddouci, Hamamache
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2015, 26 (06) : 751 - 768
123