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
Full text not available from this repository.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 |