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 条
  • [41] Parallel Genetic Algorithm for Minimum Dominating Set Problem
    Cu Nguyen Giap
    Dinh Thi Ha
    2014 INTERNATIONAL CONFERENCE ON COMPUTING, MANAGEMENT AND TELECOMMUNICATIONS (COMMANTEL), 2014, : 165 - 169
  • [42] A New Distributed Algorithm for Computing a Dominating Set on Grids
    Pisantechakool, Photchchara
    Tan, Xuehou
    FRONTIERS IN ALGORITHMICS (FAW 2015), 2015, 9130 : 217 - 228
  • [43] Self-stabilizing algorithm for minimal (α,β)-dominating set
    Saadi, Leila
    Benreguia, Badreddine
    Arar, Chafik
    Moumen, Hamouma
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY, 2022, 7 (02) : 81 - 94
  • [44] On the complexity of the minimum outer-connected dominating set problem in graphs
    Pradhan, D.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (01) : 1 - 12
  • [45] Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
    de Figueiredo, Celina M. H.
    Lopes, Raul
    de Melo, Alexsander A.
    Silva, Ana
    NETWORKS, 2024, 84 (02) : 132 - 147
  • [46] Near-optimal distributed dominating set in bounded arboricity graphs
    Dory, Michal
    Ghaffari, Mohsen
    Ilchi, Saeed
    DISTRIBUTED COMPUTING, 2024, 37 (04) : 387 - 398
  • [47] The dominating set problem is fixed parameter tractable for graphs of bounded genus
    Ellis, J
    Fan, H
    Fellows, M
    ALGORITHM THEORY - SWAT 2002, 2002, 2368 : 180 - 189
  • [48] Parameterized complexity of dominating set variants in almost cluster and split graphs
    Goyal, Dishant
    Jacob, Ashwin
    Kumar, Kaushtubh
    Majumdar, Diptapriyo
    Raman, Venkatesh
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2025, 150
  • [49] Dominating set is fixed parameter tractable in claw-free graphs
    Cygan, Marek
    Philip, Geevarghese
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Wojtaszczyk, Jakub Onufry
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) : 6982 - 7000
  • [50] Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
    Dory, Michal
    Ghaffari, Mohsen
    Ilchi, Saeed
    PROCEEDINGS OF THE 2022 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, PODC 2022, 2022, : 292 - 300
12345