AN IMPROVED HARMONY SEARCH ALGORITHM FOR MULTIPLE DOMINATING SET PROBLEMS
In graph theory, the dominating set (DS) is a subset of given graph’s vertices, where each vertex either in DS or adjacent to it. Selecting a DS of the minimum size is one of the fundamental graph theory problems, which is known as the minimum dominating set (MDS) problem. This study addresses th...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | http://utpedia.utp.edu.my/20721/1/Saad%20Adnan%20Abed%20G03549.pdf http://utpedia.utp.edu.my/20721/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Universiti Teknologi Petronas |
| Language: | English |
| Summary: | In graph theory, the dominating set (DS) is a subset of given graph’s vertices, where
each vertex either in DS or adjacent to it. Selecting a DS of the minimum size is one of
the fundamental graph theory problems, which is known as the minimum dominating
set (MDS) problem. This study addresses the MDS with two of its variants, which are
the minimum weight dominating set (MWDS), and the minimum positive influence
dominating set (MPIDS). Given the importance of dominating sets, several studies
were devoted to providing solutions for the DS problems. Due to the complexity of the
DS problems (which are categorized as NP-hard), stochastic and greedy methods were
raised. Also, these are frequently integrated with general-purpose solvers. |
|---|