A Simulated Annealing-Based Multiobjective Optimization Algorithm for Minimum Weight Minimum Connected Dominating Set Problem
Minimum connected dominating set problem is an NP-hard combinatorial optimization problem in graph theory. Finding connected dominating set is of high interest in various domains such as wireless sensor networks, optical networks, and systems biology. Its weighted variant named minimum weight connected dominating set is also useful in such applications. In this paper, we propose a simulated annealing algorithm based on a greedy heuristic for tackling a variant of the minimum connected dominating set problem and that by exploiting two objectives together namely the cardinality and the total weight of the connected dominating set. Experimental results compared to those obtained by a recent proposed research show the superiority of our approach.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationMultiobjective OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Optimization of Worker Scheduling at Logistics Depots Using Genetic Algorithms and Simulated Annealing
This paper addresses the optimization of scheduling for workers at a logistics depot using a combination of genetic algorithm and simulated annealing algorithm. The efficient scheduling of permanent and temporary workers…
SchedulingAn Upper Bound for Minimum True Matches in Graph Isomorphism with Simulated Annealing
Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard…
Combinatorial OptimizationGraph MatchingStochastic OptimizationNetwork Pruning Optimization by Simulated Annealing Algorithm
One critical problem of large neural networks is over-parameterization with a large number of weight parameters. This becomes an obstacle to implement networks in edge devices as well as limiting the development of indus…
Network PruningSAGRAD: A Program for Neural Network Training with Simulated Annealing and the Conjugate Gradient Method
SAGRAD (Simulated Annealing GRADient), a Fortran 77 program for computing neural networks for classification using batch learning, is discussed. Neural network training in SAGRAD is based on a combination of simulated an…
Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization
Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning--assiste…