Voir la notice de l'article provenant de la source Numdam
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.
@article{RO_2013__47_3_199_0,
author = {Laforest, Christian and Phan, Raksmey},
title = {Solving the {Minimum} {Independent} {Domination} {Set} {Problem} in {Graphs} by {Exact} {Algorithm} and {Greedy} {Heuristic}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {199--221},
publisher = {EDP-Sciences},
volume = {47},
number = {3},
year = {2013},
doi = {10.1051/ro/2013034},
mrnumber = {3143749},
zbl = {1282.05180},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2013034/}
}
TY - JOUR AU - Laforest, Christian AU - Phan, Raksmey TI - Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2013 SP - 199 EP - 221 VL - 47 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2013034/ DO - 10.1051/ro/2013034 LA - en ID - RO_2013__47_3_199_0 ER -
%0 Journal Article %A Laforest, Christian %A Phan, Raksmey %T Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic %J RAIRO - Operations Research - Recherche Opérationnelle %D 2013 %P 199-221 %V 47 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2013034/ %R 10.1051/ro/2013034 %G en %F RO_2013__47_3_199_0
Laforest, Christian; Phan, Raksmey. Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 3, pp. 199-221. doi: 10.1051/ro/2013034
Cité par Sources :