TY - GEN
T1 - Heuristic Approach for Solving the Dual Dominating Set Problem With Conflicts
AU - Jovanovic, Raka
AU - Aličić, Denis
AU - Sezer, Nurettin
AU - Marić, Miroslav
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
PY - 2026
Y1 - 2026
N2 - This paper introduces a novel combinatorial optimization problem, the Dual Dominating Set Problem with Conflicts (DDSP-C), which extends the classical Dominating Set Problem by requiring the identification of two disjoint dominating sets under pairwise conflict constraints. Such constraints prohibit specific node pairs from appearing in different dominating sets, reflecting practical considerations in facility location and resource allocation. We present an Integer Linear Programming (ILP) formulation to model the problem precisely and propose a metaheuristic solution approach based on the Greedy Randomized Adaptive Search Procedure (GRASP). The GRASP algorithm combines a randomized greedy construction with a local search phase, aiming to efficiently generate high-quality solutions. Experiments on random instances show the approach’s effectiveness and reveal insights into problem complexity across different graph densities and conflict levels.
AB - This paper introduces a novel combinatorial optimization problem, the Dual Dominating Set Problem with Conflicts (DDSP-C), which extends the classical Dominating Set Problem by requiring the identification of two disjoint dominating sets under pairwise conflict constraints. Such constraints prohibit specific node pairs from appearing in different dominating sets, reflecting practical considerations in facility location and resource allocation. We present an Integer Linear Programming (ILP) formulation to model the problem precisely and propose a metaheuristic solution approach based on the Greedy Randomized Adaptive Search Procedure (GRASP). The GRASP algorithm combines a randomized greedy construction with a local search phase, aiming to efficiently generate high-quality solutions. Experiments on random instances show the approach’s effectiveness and reveal insights into problem complexity across different graph densities and conflict levels.
KW - Conflicts
KW - Dominating set problem
KW - mathematical programming
UR - https://www.scopus.com/pages/publications/105039045406
U2 - 10.1007/978-3-032-19675-0_3
DO - 10.1007/978-3-032-19675-0_3
M3 - Conference contribution
AN - SCOPUS:105039045406
SN - 9783032196743
T3 - Lecture Notes in Networks and Systems
SP - 20
EP - 29
BT - ICT
A2 - Joshi, Amit
A2 - Ragel, Roshan G.
A2 - Kartik, S.
PB - Springer Science and Business Media Deutschland GmbH
T2 - 10th International Conference on Information and Communication Technology for Competitive Strategies, ICTCS 2025
Y2 - 15 December 2025 through 17 December 2025
ER -