Computer Science – Data Structures and Algorithms
Scientific paper
2010-09-07
Computer Science
Data Structures and Algorithms
Full version. A preliminary version appeared in the proceedings of WG 2006
Scientific paper
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower bound of \Omega(1.3247^n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.
Gaspers Serge
Liedloff Mathieu
No associations
LandOfFree
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-705053