Fomin, Fedor V. and Grandoni, Fabrizio and Kratsch, Dieter
(2008)
*
Solving Connected Dominating Set Faster than 2^n.
*
*Algorithmica*, 52 (2).
pp. 153-166.
ISSN 1432-0541

## Abstract

In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves. Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2 n ) algorithm that enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such a difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly. In this paper we break the 2 n barrier, by presenting a simple O(1.9407 n ) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique.

Item Type: | Scientific journal article, Newspaper article or Magazine article |
---|---|

Uncontrolled Keywords: | Exponential-time exact algorithm; NP-hard problem; Connected dominating set; Maximum leaf spanning tree |

Subjects: | Computer sciences |

Depositing User: | Fabrizio Grandoni |

Date Deposited: | 14 Mar 2014 09:04 |

Last Modified: | 23 May 2016 14:50 |

URI: | http://repository.supsi.ch/id/eprint/4502 |

### Actions (login required)

View Item |