Publications in Scientific Journals:
S. Gaspers, M. Liedloff:
"A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set";
Discrete Mathematics & Theoretical Computer Science,
Vol. 14
(2012),
No. 1;
29
- 42.
English abstract:
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.4423n )-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.3569n ). Furthermore, we give a lower bound of Ω(1.3247n ) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.
Keywords:
Exponential time algorithms, minimum independent dominating set, minimum maximal independent set
Related Projects:
Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Created from the Publication Database of the Vienna University of Technology.