Journal
ACM TRANSACTIONS ON ALGORITHMS
Volume 5, Issue 1, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1435375.1435384
Keywords
Exact exponential algorithms; listing algorithms; measure and conquer; minimum dominating set; minimum set cover; domatic number
Ask authors/readers for more resources
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)/root 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available