RT Journal Article
T1 An iterated greedy algorithm for finding the minimum dominating set in graphs
A1 Casado, Alejandra
A1 Bermudo Navarrete, Sergio
A1 López Sánchez, Ana Dolores
A1 Hernández-Díaz, Alfredo G.
K1 Domination number
K1 Exact algorithm
K1 Exact algorithm
K1 Iterated greedy
K1 Greedy heuristics
K1 Minimum dominating set
AB A dominating set in a graph is a set of vertices such that every vertex outside the set is adjacent to a vertex in the set. The domination number is the minimum cardinality of a dominating set in the graph. The problem of finding the minimum dominating set is a combinatorial optimization problem that has been proved to be NP-hard. Given the difficulty of this problem, an Iterated Greedy algorithm is proposed for its solution and it is compared to the solution given by an exact algorithm and by the state-of-art algorithms. Computational results show that the proposal is able to find optimal or near-optimal solutions within a short computational time. Specifically, from the set of instances which can be optimally solved, the proposed method presents an average deviation of 0.04%. Regarding the more complex set of instances, where the exact method is not able to reach the optimal value, the proposed method achieves an average deviation of 1.23% with respect to the best-known solution.
PB Elsevier
YR 2023
FD 2023-12-23
LK https://hdl.handle.net/10433/22300
UL https://hdl.handle.net/10433/22300
LA en
NO A. Casado, S. Bermudo, A.D. López-Sánchez, J. Sánchez-Oro, An iterated greedy algorithm for finding the minimum dominating set in graphs, Mathematics and Computers in Simulation, Volume 207, 2023, Pages 41-58, ISSN 0378-4754, https://doi.org/10.1016/j.matcom.2022.12.018.
NO Departamento de Economía, Métodos cuantitativos e Historia Económica. Universidad Pablo de Olavide.
DS RIO
RD May 8, 2026