A note on the complexity of minimum dominating set

2005/04/14 by Fabrizio Grandoni · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Discrete mathematics #Dominating set #Efficient algorithm #Graph #Mathematics #Optimization and Search Problems #Set (abstract data type) #Simple (philosophy) #Theoretical computer science #Time complexity

paper · pdf · doi:10.1016/j.jda.2005.03.002

openalex publication_date 2005/04/14 · crossref created 2005/04/14 · crossref issued 2006/06/01 · crossref published 2006/06/01 · crossref published-print 2006/06/01 · crossref deposited 2019/01/27 · openalex created_date 2025/10/10 · crossref indexed 2026/07/09 · openalex updated_date 2026/07/31

Citations

• An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
• An improved exponential-time algorithm for k -SAT
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set

Cited by

• Combinatorial bounds via measure and conquer
• Inclusion/Exclusion Meets Measure and Conquer
• Dominating set [wikipedia]