A note on the complexity of minimum dominating set

DOI10.1016/J.JDA.2005.03.002MaRDI QIDQ2458924zbMATH OpenOpenAlexFDO

Authors Fabrizio Grandoni

Publication date 5 November 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2005.03.002

zbMATH Keywords

dominating setexact algorithmsset cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

Minimum dominating set is one of the most basic NP-hard problems in graph theory. The currently fastest algorithm to solve this problem for graphs on \(n\) vertices is the trivial \(\Omega (2^n)\) algorithm which enumerates and checks all subsets of the set of vertices. In this paper a simple algorithm which solves this problem in \(O(1.81^n)\) time is presented.

Recommendations

• A polynomial-time approximation to a minimum dominating set in a graph
• On the complexity of dominating set problems related to the minimum all-ones problem
• On the complexity of the minimum outer-connected dominating set problem in graphs
• Parameterized complexity of minimum membership dominating set
• Parameterized complexity of minimum membership dominating set
• The algorithmic complexity of minus domination in graphs
• Algorithms and Computation
• On approximating the minimum independent dominating set
• Minimum dominating set approximation in graphs of bounded arboricity
• scientific article; zbMATH DE number 842019

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Algorithms for maximum independent sets
• An improved fixed-parameter algorithm for vertex cover
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305487 (Why is no real title available?)
• scientific article; zbMATH DE number 1306877 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• New Upper Bounds for Maximum Satisfiability
• On efficient fixed-parameter algorithms for weighted vertex cover
• Vertex cover: Further observations and further improvements

Cited in

(34)

• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• On two techniques of combining branching and treewidth
• A randomized algorithm for determining dominating sets in graphs of maximum degree five
• Pathwidth of cubic graphs and exact algorithms
• On finding a minimum dominating set in a tournament
• The algorithmic complexity of minus domination in graphs
• A heuristic approximation algorithm of minimum dominating set based on rough set theory
• Inclusion/exclusion meets measure and conquer
• On the complexity of Mixed Dominating Set
• Computing optimal Steiner trees in polynomial space
• Exact algorithms for maximum induced matching
• Sharp separation and applications to exact and parameterized algorithms
• An exact algorithm for the minimum dominating clique problem
• Membrane computing to enhance time efficiency of minimum dominating set
• Improved worst-case complexity for the MIN 3-SET COVERING problem
• scientific article; zbMATH DE number 5990006 (Why is no real title available?)
• Spotting trees with few leaves
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• Exact algorithms for dominating set
• scientific article; zbMATH DE number 1735803 (Why is no real title available?)
• scientific article; zbMATH DE number 842019 (Why is no real title available?)
• scientific article; zbMATH DE number 867663 (Why is no real title available?)
• Combinatorial bounds via measure and conquer
• On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Improved bounds for online dominating sets of trees
• Spotting trees with few leaves
• Graph-Theoretic Concepts in Computer Science
• Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
• Exponential time algorithms for the \textsc{minimum dominating set} problem on some graph classes
• Benchmarking ORCA PT-1 boson sampler in simulation
• Solving connected dominating set faster than \(2^n\)
• Finding a dominating set on bipartite graphs

This page was built for publication: A note on the complexity of minimum dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2458924)