A Hybrid Metaheuristic for the Minimum Weight Dominating Set Problem

Simple item page
dc.contributor.authorLOUANAS, Salma
dc.date.accessioned2018-01-31T08:49:58Z
dc.date.available2018-01-31T08:49:58Z
dc.date.issued2017
dc.description.abstractIn 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.en_US
dc.identifier.urihttp://dspace.univ-msila.dz:8080//xmlui/handle/123456789/1910
dc.language.isoenen_US
dc.publisherFACULTE Mathématique et Informatique - UNIVERSITE MOHAMED BOUDIAF - M’SILAen_US
dc.subjectNP-Complete,Carousel Greedy,Local Search,minimum weight dominating set problemen_US
dc.titleA Hybrid Metaheuristic for the Minimum Weight Dominating Set Problemen_US
dc.typeThesisen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Louanas salma.pdf
Size:
1.59 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Master Thesis