2008/11/01 by Fedor V. Fomin, Fabrizio Grandoni, A. V. Pyatkin +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Combinatorics #Divide and conquer algorithms #Mathematics #Measure (data warehouse) #Discrete mathematics #Upper and lower bounds #Graph #Algorithm #Computer science #Data mining
paper · doi:10.1145/1435375.1435384
openalex publication_date 2008/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/21
We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O (1.7159 n ). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159 n , thus improving on the trivial O (2 n /√ n ) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. Based on this result, we derive an O (2.8718 n ) algorithm for the domatic number problem.