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 条
  • [21] MINIMUM DOMINATING SET OF QUEENS: A trivial programming exercise?
    Fernau, Henning
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (04) : 308 - 318
  • [22] Minimum Connected Dominating set for Certain Circulant Networks
    Parthiban, N.
    Rajasingh, Indra
    Rajan, R. Sundara
    3RD INTERNATIONAL CONFERENCE ON RECENT TRENDS IN COMPUTING 2015 (ICRTC-2015), 2015, 57 : 587 - 591
  • [23] Hybrid metaheuristic algorithms for minimum weight dominating set
    Potluri, Anupama
    Singh, Alok
    APPLIED SOFT COMPUTING, 2013, 13 (01) : 76 - 88
  • [24] Vertices contained in every minimum dominating set of a tree
    Mynhardt, CM
    JOURNAL OF GRAPH THEORY, 1999, 31 (03) : 163 - 177
  • [25] Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes
    Eto, Hiroshi
    Kawahara, Hiroyuki
    Miyano, Eiji
    Nonoue, Natsuki
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2018, E101D (03): : 574 - 581
  • [26] Optimal Metric Search Is Equivalent to the Minimum Dominating Set Problem
    Hetland, Magnus Lie
    SIMILARITY SEARCH AND APPLICATIONS, SISAP 2020, 2020, 12440 : 111 - 125
  • [27] An improved exact algorithm for minimum dominating set in chordal graphs
    Abu-Khzam, Faisal N.
    INFORMATION PROCESSING LETTERS, 2022, 174
  • [28] PTAS for the minimum weighted dominating set in growth bounded graphs
    Zhong Wang
    Wei Wang
    Joon-Mo Kim
    Bhavani Thuraisingham
    Weili Wu
    Journal of Global Optimization, 2012, 54 : 641 - 648
  • [29] PTAS for the minimum weighted dominating set in growth bounded graphs
    Wang, Zhong
    Wang, Wei
    Kim, Joon-Mo
    Thuraisingham, Bhavani
    Wu, Weili
    JOURNAL OF GLOBAL OPTIMIZATION, 2012, 54 (03) : 641 - 648
  • [30] A polynomial-time approximation to a minimum dominating set in a graph
    Mira, Frank angel Hernandez
    Inza, Ernesto Parra
    Almira, Jose Maria Sigarreta
    Vakhania, Nodari
    THEORETICAL COMPUTER SCIENCE, 2022, 930 : 142 - 156
12345