A Hybrid Metaheuristic for the Minimum Weight Dominating Set Problem

Loading...
Thumbnail Image

Date

2017

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

Citation

Collections