Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications

Fomin, Fedor V. and Grandoni, Fabrizio and Pyatkin, Artem V. and Stepanov, Alexey A. (2008) Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Transactions on Algorithms, 5 (1). ISSN 1549-6325

Full text not available from this repository.

Abstract

We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O(1.7159n). 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.7159n, thus improving on the trivial O(2n/&sqrt;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.8718n) algorithm for the domatic number problem.

Actions (login required)

View Item View Item