A strengthened analysis of an algorithm for DOMINATING SET in planar graphs

被引：0
|
作者：
Hagerup, Torben [1 ]
机构：
[1] Univ Augsburg, Inst Informat, D-86135 Augsburg, Germany
来源：
DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 06期
关键词：
Dominating set; Planar graph; Parameterized complexity; PARAMETERIZED ALGORITHMS;
D O I：
10.1016/j.dam.2010.10.004
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Alber et al. presented an algorithm for computing a dominating set of size at most k, if one exists, in an undirected planar n-vertex graph and bounded its execution time by O(8(k)0). Here it is shown that the algorithm performs better than claimed by its authors. More significantly, if k <= n/19, even a much simplified version of the algorithm runs in O(7(k)n) time. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：793 / 798
页数：6
相关论文
共 50 条
  • [1] A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
    Wawrzyniak, Wojciech
    INFORMATION PROCESSING LETTERS, 2014, 114 (03) : 94 - 98
  • [2] Refined search tree technique for DOMINATING SET on planar graphs
    Alber, J
    Fan, HB
    Fellows, MR
    Fernau, H
    Niedermeier, R
    Rosamond, F
    Stege, U
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2001, 2001, 2136 : 111 - 122
  • [3] A refined search tree technique for Dominating Set on planar graphs
    Alber, J
    Fan, HB
    Fellows, MR
    Fernau, H
    Niedermeier, R
    Rosamond, F
    Stege, U
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 71 (04) : 385 - 405
  • [4] Distributed Dominating Set Approximations beyond Planar Graphs
    Amiri, Saeed Akhoondian
    Schmid, Stefan
    Siebertz, Sebastian
    ACM TRANSACTIONS ON ALGORITHMS, 2019, 15 (03)
  • [5] PTASs for secure dominating set in planar graphs and growth-bounded graphs
    Li, Ke
    Zhang, Zhao
    DISCRETE APPLIED MATHEMATICS, 2024, 357 : 343 - 351
  • [6] Brief Announcement: A LOCAL Constant Approximation Factor Algorithm for Minimum Dominating Set of Certain Planar Graphs
    Alipour, Sharareh
    Jafari, Amir
    PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, : 501 - 502
  • [7] Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs
    Hilke, Miikka
    Lenzen, Christoph
    Suomela, Jukka
    PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, : 344 - 346
  • [8] A local approximation algorithm for minimum dominating set problem in anonymous planar networks
    Wojciech Wawrzyniak
    Distributed Computing, 2015, 28 : 321 - 331
  • [9] A local approximation algorithm for minimum dominating set problem in anonymous planar networks
    Wawrzyniak, Wojciech
    DISTRIBUTED COMPUTING, 2015, 28 (05) : 321 - 331
  • [10] On the Number of -Dominating Independent Sets in Planar Graphs
    Taletskii D.S.
    Journal of Applied and Industrial Mathematics, 2024, 18 (01) : 167 - 178
12345