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 条
  • [1] Parameterized Complexity of Minimum Membership Dominating Set
    Agrawal, Akanksha
    Choudhary, Pratibha
    Narayanaswamy, N. S.
    Nisha, K. K.
    Ramamoorthi, Vijayaragunathan
    ALGORITHMICA, 2023, 85 (11) : 3430 - 3452
  • [2] Parameterized Complexity of Minimum Membership Dominating Set
    Akanksha Agrawal
    Pratibha Choudhary
    N. S. Narayanaswamy
    K. K. Nisha
    Vijayaragunathan Ramamoorthi
    Algorithmica, 2023, 85 : 3430 - 3452
  • [3] On the complexity of the minimum outer-connected dominating set problem in graphs
    Pradhan, D.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (01) : 1 - 12
  • [4] On the Parameterized Complexity of Approximating Dominating Set
    Karthik, C. S.
    Laekhanukit, Bundit
    Manurangsi, Pasin
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 1283 - 1296
  • [5] On the Parameterized Complexity of Approximating Dominating Set
    Karthik, C. S.
    Laekhanukit, Bundit
    Manurangsi, Pasin
    JOURNAL OF THE ACM, 2019, 66 (05)
  • [6] On the complexity of the minimum outer-connected dominating set problem in graphs
    D. Pradhan
    Journal of Combinatorial Optimization, 2016, 31 : 1 - 12
  • [7] The complexity of dominating set reconfiguration
    Haddadan, Arash
    Ito, Takehiro
    Mouawad, Amer E.
    Nishimura, Naomi
    Ono, Hirotaka
    Suzuki, Akira
    Tebbal, Youcef
    THEORETICAL COMPUTER SCIENCE, 2016, 651 : 37 - 49
  • [8] Approximating a Minimum Dominating Set by Purification
    Inza, Ernesto Parra
    Vakhania, Nodari
    Almira, Jose Maria Sigarreta
    Hernandez-Aguilar, Jose Alberto
    ALGORITHMS, 2024, 17 (06)
  • [9] The probabilistic minimum dominating set problem
    Boria, Nicolas
    Murat, Cecile
    Paschos, Vangelis Th.
    DISCRETE APPLIED MATHEMATICS, 2018, 234 : 93 - 113
  • [10] Statistical Mechanics of the Minimum Dominating Set Problem
    Zhao, Jin-Hua
    Habibulla, Yusupjan
    Zhou, Hai-Jun
    JOURNAL OF STATISTICAL PHYSICS, 2015, 159 (05) : 1154 - 1174
12345