Volume 47, Number 3, July-September 2013
|Page(s)||199 - 221|
|Published online||02 May 2013|
Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic∗
LIMOS, CNRS UMR 6158, Université Blaise Pascal, Clermont–Ferrand Campus des
Cézeaux, 24 avenue des Landais, 63173 Aubière Cedex, France.
Accepted: 19 March 2013
In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including cuts in the search process. We then experiment it and show that it is able to solve almost all instances up to 50 vertices in reasonable time and some instances up to several hundreds of vertices. To go further and to treat larger graphs, we analyze a greedy heuristic. We show that it often gives good (sometimes optimal) results in large instances up to 60 000 vertices in less than 20 s. That sort of heuristic is a good approach to get an initial solution for our exact method. We also describe and analyze some of its worst cases.
Mathematics Subject Classification: 05C69 / 05C85
Key words: Combinatorial optimization / heuristics / exact algorithm / worst case analysis / experimentations / independent dominating set in graphs
© EDP Sciences, ROADEF, SMAI, 2013
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.