A Hybrid Metaheuristic for the Minimum Weight Dominating Set Problem
Loading...
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
FACULTE Mathématique et Informatique - UNIVERSITE MOHAMED BOUDIAF - M’SILA
Abstract
In this memory, we deal with a classical problem in graph theory the minimum
weight dominating set problem. The latter belong to the class of NP-complete problems
where no efficient algorithm is known to solve it to optimality. We have implemented a
hybrid algorithm that combines a modified carousel greedy algorithm and local search
to give near optimal solutions within a reasonable computation-time to this problem.
Experimental results show that the algorithm has competitive performance with a
recent published ant colony optimization approach.
Description
Keywords
NP-Complete,Carousel Greedy,Local Search,minimum weight dominating set problem