We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic.
- Authors
Laforest, Christian; Phan, Raksmey
- Abstract
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.
- Subjects
GRAPH theory; GREEDY algorithms; HEURISTIC programming; PROBLEM solving; SET theory; MATHEMATICAL optimization; COMPUTATIONAL complexity
- Publication
RAIRO -- Operations Research, 2013, Vol 47, Issue 3, p199
- ISSN
0399-0559
- Publication type
Article
- DOI
10.1051/ro/2013034