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.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 09:05 |
| Last Modified: | 23 May 2016 14:56 |
| URI: | http://repository.supsi.ch/id/eprint/4505 |
Actions (login required)
 |
View Item |