Scholarlink

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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Heuristic Approach for Solving the Dual Dominating Set Problem With Conflicts

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Raka Jovanovic,
  • Denis Aličić,
  • Nurettin Sezer,
  • Miroslav Marić

摘要

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.