A note on the complexity of minimum dominating set

DOI10.1016/j.jda.2005.03.002zbMath1127.05070OpenAlexW1999216089MaRDI QIDQ2458924

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 setset coverexact algorithms

Mathematics Subject Classification ID

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

Related Items (20)

Spotting Trees with Few Leaves ⋮ Spotting Trees with Few Leaves ⋮ Membrane computing to enhance time efficiency of minimum dominating set ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Improved worst-case complexity for the MIN 3-SET COVERING problem ⋮ Computing optimal Steiner trees in polynomial space ⋮ Exact algorithms for maximum induced matching ⋮ Exact algorithms for dominating set ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ An exact algorithm for the minimum dominating clique problem ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Inclusion/exclusion meets measure and conquer ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Finding a dominating set on bipartite graphs ⋮ 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 ⋮ Unnamed Item ⋮ A randomized algorithm for determining dominating sets in graphs of maximum degree five ⋮ Pathwidth of cubic graphs and exact algorithms

Cites Work

• An improved fixed-parameter algorithm for vertex cover
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Vertex Cover: Further Observations and Further Improvements
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• On efficient fixed-parameter algorithms for weighted vertex cover
• New Upper Bounds for Maximum Satisfiability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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