Scholarlink

<p>The Minimum Weighted Dominating Set (MWDS) problem is a challenging hard graph optimization problem and it has various real-world applications, particularly in network design and communications. In this paper, a novel, discrete swarm optimization-based local search algorithm is developed for MWDS. This approach integrates the jumping particle swarm optimization approach with two new local search strategies based on cost ratio and neighbourhood search, with this, the proposed JPSWD efficiently identifies the solution space by avoiding local optimum. Simulation results carried out on extensive datasets suggest that the performance of JPSWD is better than that of the existing algorithms. This notable improvement is particularly evident in the context of execution time and computational cost, which are critical factors we have considered over other algorithms. A statistical analysis based on algorithms’ ranking further substantiates the better performance of JPSWD, and marking it as a better alternative for tackling the MWDS problem.</p>

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

A hybrid jumping swarm optimization based local search approach for minimum weighted dominating set problem

  • 期刊论文

  • 发表日期：

    2025年6月25日

查看全文
  • G. Maheswari,
  • S. Balaji

摘要

The Minimum Weighted Dominating Set (MWDS) problem is a challenging hard graph optimization problem and it has various real-world applications, particularly in network design and communications. In this paper, a novel, discrete swarm optimization-based local search algorithm is developed for MWDS. This approach integrates the jumping particle swarm optimization approach with two new local search strategies based on cost ratio and neighbourhood search, with this, the proposed JPSWD efficiently identifies the solution space by avoiding local optimum. Simulation results carried out on extensive datasets suggest that the performance of JPSWD is better than that of the existing algorithms. This notable improvement is particularly evident in the context of execution time and computational cost, which are critical factors we have considered over other algorithms. A statistical analysis based on algorithms’ ranking further substantiates the better performance of JPSWD, and marking it as a better alternative for tackling the MWDS problem.