A note on the complexity of minimum dominating set

被引：71
作者：
Grandoni, Fabrizio [1 ]
机构：
[1] Max Planck Inst Informatik, Stuhlsatzenhausweg 85, D-66123 Saarbrucken, Germany
来源：
JOURNAL OF DISCRETE ALGORITHMS | 2006年 / 4卷 / 02期
关键词：
Dominating set; Set cover; Exact algorithms;
D O I：
10.1016/j.jda.2005.03.002
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n nodes is the trivial Omega(2(n)) algorithm which enumerates and checks all the subsets of nodes. In this paper we present a simple algorithm which solves this problem in O(1.81(n)) time. (C) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：209 / 214
页数：6
相关论文
共 50 条
  • [31] The Parameterized Complexity of Dominating Set and Friends Revisited for Structured Graphs
    Misra, Neeldhara
    Rathi, Piyush
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2019, 11532 : 299 - 310
  • [32] A complexity dichotomy and a new boundary class for the dominating set problem
    Malyshev, D. S.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (01) : 226 - 243
  • [33] A complexity dichotomy and a new boundary class for the dominating set problem
    D. S. Malyshev
    Journal of Combinatorial Optimization, 2016, 32 : 226 - 243
  • [34] Towards efficient local search for the minimum total dominating set problem
    Hu, Shuli
    Liu, Huan
    Wang, Yupan
    Li, Ruizhi
    Yin, Minghao
    Yang, Nan
    APPLIED INTELLIGENCE, 2021, 51 (12) : 8753 - 8767
  • [35] A hybrid evolutionary algorithm with guided mutation for minimum weight dominating set
    Sachchida Nand Chaurasia
    Alok Singh
    Applied Intelligence, 2015, 43 : 512 - 529
  • [36] A hybrid evolutionary algorithm with guided mutation for minimum weight dominating set
    Chaurasia, Sachchida Nand
    Singh, Alok
    APPLIED INTELLIGENCE, 2015, 43 (03) : 512 - 529
  • [37] Towards efficient local search for the minimum total dominating set problem
    Shuli Hu
    Huan Liu
    Yupan Wang
    Ruizhi Li
    Minghao Yin
    Nan Yang
    Applied Intelligence, 2021, 51 : 8753 - 8767
  • [38] The Minimum Weight Dominating Set Problem under Hybrid Uncertain Environments
    Wang, Chenyin
    Luo, Dongling
    Zeng, Mowei
    Yi, Yang
    Zhou, Xiaocong
    ADVANCED DEVELOPMENT IN AUTOMATION, MATERIALS AND MANUFACTURING, 2014, 624 : 545 - 548
  • [39] Solving Minimum Dominating Set in Multiplex Networks Using Learning Automata
    Khomami, Mohammad Mehdi Daliri
    Rezvanian, Alireza
    Saghiri, Ali Mohammad
    Meybodi, Mohammad Reza
    2021 26TH INTERNATIONAL COMPUTER CONFERENCE, COMPUTER SOCIETY OF IRAN (CSICC), 2021,
  • [40] Parameterized dominating set problem in chordal graphs: complexity and lower bound
    Liu, Chunmei
    Song, Yinglei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (01) : 87 - 97
12345