Geodesic
Integer Linear Programming Models and Greedy Heuristic for the Minimum Weighted Independent Dominating Set Problem
Serdica Journal of Computing, Tome 17 (2024) no. 2, pp. 117-136 Cet article a éte moissonné depuis la source Bulgarian Digital Mathematics Library

Voir la notice de l'article

This paper explores the Minimum Weighted Independent Dominating Set Problem and proposes novel approaches to tackle it. Namely, two integer linear programming formulations and a fast greedy heuristic as an alternative approach are proposed. Extensive computational experiments are conducted to evaluate the performance of these approaches on the established set of benchmark instances for the problem. The obtained results demonstrate that the introduced integer linear programming models are able to achieve optimal solutions on all instances with 100 nodes and significantly outperform existing exact methods on numerous other instances. Additionally, the greedy heuristic exhibits superior performance compared to competing greedy heuristics, particularly on random graphs. These findings suggest promising directions for future research, including the integration of these methods into hybrid algorithms or metaheuristic frameworks.
Keywords: Integer linear programming, Greedy heuristic, Domination problems 
@article{SJC_2024_17_2_a2,
     author = {Kapunac, Stefan},
     title = {Integer {Linear} {Programming} {Models} and {Greedy} {Heuristic} for the {Minimum} {Weighted} {Independent} {Dominating} {Set} {Problem}},
     journal = {Serdica Journal of Computing},
     pages = {117--136},
     year = {2024},
     volume = {17},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2024_17_2_a2/}
}
TY  - JOUR
AU  - Kapunac, Stefan
TI  - Integer Linear Programming Models and Greedy Heuristic for the Minimum Weighted Independent Dominating Set Problem
JO  - Serdica Journal of Computing
PY  - 2024
SP  - 117
EP  - 136
VL  - 17
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SJC_2024_17_2_a2/
LA  - en
ID  - SJC_2024_17_2_a2
ER  - 
%0 Journal Article
%A Kapunac, Stefan
%T Integer Linear Programming Models and Greedy Heuristic for the Minimum Weighted Independent Dominating Set Problem
%J Serdica Journal of Computing
%D 2024
%P 117-136
%V 17
%N 2
%U http://geodesic.mathdoc.fr/item/SJC_2024_17_2_a2/
%G en
%F SJC_2024_17_2_a2
Kapunac, Stefan. Integer Linear Programming Models and Greedy Heuristic for the Minimum Weighted Independent Dominating Set Problem. Serdica Journal of Computing, Tome 17 (2024) no. 2, pp. 117-136. http://geodesic.mathdoc.fr/item/SJC_2024_17_2_a2/