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 条
  • [21] On dominating set of some subclasses of string graphs
    Chakraborty, Dibyayan
    Das, Sandip
    Mukherjee, Joydeep
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2022, 107
  • [22] Computational study on planar dominating set problem
    Marzban, Marjan
    Gu, Qian-Ping
    Jia, Xiaohua
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (52) : 5455 - 5466
  • [23] Parameterized dominating set problem in chordal graphs: complexity and lower bound
    Liu, Chunmei
    Song, Yinglei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (01) : 87 - 97
  • [24] An Efficient Algorithm for Power Dominating Set
    Blaesius, Thomas
    Goettlicher, Max
    ALGORITHMICA, 2025, 87 (03) : 344 - 376
  • [25] Parameterized dominating set problem in chordal graphs: complexity and lower bound
    Chunmei Liu
    Yinglei Song
    Journal of Combinatorial Optimization, 2009, 18 : 87 - 97
  • [26] Liar's Dominating Set in Unit Disk Graphs
    Jallu, Ramesh K.
    Jena, Sangram K.
    Das, Gautam K.
    COMPUTING AND COMBINATORICS (COCOON 2018), 2018, 10976 : 516 - 528
  • [27] Dominating set and hamiltonicity in claw-heavy graphs
    Cai, Junqing
    ARS COMBINATORIA, 2018, 141 : 21 - 27
  • [28] Approximating the minimum independent dominating set in perturbed graphs
    Tong, Weitian
    Goebel, Randy
    Lin, Guohui
    THEORETICAL COMPUTER SCIENCE, 2014, 554 : 275 - 282
  • [29] LOSSY KERNELS FOR CONNECTED DOMINATING SET ON SPARSE GRAPHS
    Eiben, Eduard
    Kumar, Mithilesh
    Mouawad, Amer E.
    Panolan, Fahad
    Siebertz, Sebastian
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) : 1743 - 1771
  • [30] FAST ALGORITHMS FOR THE DOMINATING SET PROBLEM ON PERMUTATION GRAPHS
    TSAI, KH
    HSU, WL
    ALGORITHMICA, 1993, 9 (06) : 601 - 614
12345