Serge Gaspers ; Mathieu Liedloff - A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set

dmtcs:563 - Discrete Mathematics & Theoretical Computer Science, February 7, 2012, Vol. 14 no. 1 -
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set

Authors: Serge Gaspers 1; Mathieu Liedloff ORCID-iD2

  • 1 Institute of Information Systems
  • 2 Laboratoire d'Informatique Fondamentale d'Orléans

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.

Volume: Vol. 14 no. 1
Section: Graph and Algorithms
Published on: February 7, 2012
Accepted on: June 9, 2015
Submitted on: September 7, 2010
Keywords: [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 0802.2827
Source : ScholeXplorer IsRelatedTo DOI 10.4230/lipics.stacs.2008.1329
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.0802.2827
  • 10.48550/arxiv.0802.2827
  • 10.4230/lipics.stacs.2008.1329
  • 0802.2827
Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set

Consultation statistics

This page has been seen 343 times.
This article's PDF has been downloaded 337 times.