Scholarlink

<p>This paper introduces a metaheuristic approach for solving the Maximum Disjoint Dominating Sets Problem (MDDSP). The problem is initially addressed using a Greedy Randomized Adaptive Search Procedure (GRASP), which incorporates two distinct local search strategies. The first employs a standard swap neighborhood, while the second utilizes a novel neighborhood structure designed to complement and enhance the effectiveness of the swap-based approach. To further improve performance, the GRASP is extended into the Fixed Set Search (FSS) metaheuristic, which integrates a learning mechanism to guide the search process. Computational experiments are conducted on various graph types, including random, Watts–Strogatz, and Barabási–Albert graphs, with up to 1,000 vertices and differing densities. The results show that the FSS significantly outperforms state-of-the-art methods, such as the multi-constructor Construct, Merge, Solve, and Adapt (CMSA) algorithm, delivering superior solution quality across nearly all test instances. The enhanced local search techniques proved particularly effective on dense graphs. Furthermore, the results confirm that the FSS consistently improves the performance of the underlying GRASP, highlighting its robustness and efficiency for solving the MDDSP.</p>

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

Extending GRASP towards an improved Fixed Set Search for solving the maximum disjoint dominating sets problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月29日

查看全文
  • Raka Jovanovic,
  • Stefan Voß

摘要

This paper introduces a metaheuristic approach for solving the Maximum Disjoint Dominating Sets Problem (MDDSP). The problem is initially addressed using a Greedy Randomized Adaptive Search Procedure (GRASP), which incorporates two distinct local search strategies. The first employs a standard swap neighborhood, while the second utilizes a novel neighborhood structure designed to complement and enhance the effectiveness of the swap-based approach. To further improve performance, the GRASP is extended into the Fixed Set Search (FSS) metaheuristic, which integrates a learning mechanism to guide the search process. Computational experiments are conducted on various graph types, including random, Watts–Strogatz, and Barabási–Albert graphs, with up to 1,000 vertices and differing densities. The results show that the FSS significantly outperforms state-of-the-art methods, such as the multi-constructor Construct, Merge, Solve, and Adapt (CMSA) algorithm, delivering superior solution quality across nearly all test instances. The enhanced local search techniques proved particularly effective on dense graphs. Furthermore, the results confirm that the FSS consistently improves the performance of the underlying GRASP, highlighting its robustness and efficiency for solving the MDDSP.