Advertisement
Published in:
2005 | OriginalPaper | Chapter
Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach
Authors : Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, Alexey A. Stepanov
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We show that the number of minimal dominating sets in a graph on
n
vertices is at most 1.7697
n
, thus improving on the trivial
$\mathcal{O}(2^{n}/\sqrt{n})$
bound. Our result makes use of the measure and conquer technique from exact algorithms, and can be easily turned into an
$\mathcal{O}(1.7697^{n})$
listing algorithm.
Based on this result, we derive an
$\mathcal{O}(2.8805^{n})$
algorithm for the domatic number problem, and an
$\mathcal{O}(1.5780^{n})$
algorithm for the minimum-weight dominating set problem. Both algorithms improve over the previous algorithms.