AN IMPROVED HARMONY SEARCH ALGORITHM FOR MULTIPLE DOMINATING SET PROBLEMS

• Main Author: ABED, SAAD ADNAN
• Format: Thesis
• Language: English
• Published: 2021
• Subjects: QA Mathematics; QA75 Electronic computers. Computer science
• Online Access: http://utpedia.utp.edu.my/20721/1/Saad%20Adnan%20Abed%20G03549.pdf; http://utpedia.utp.edu.my/20721/
• Institution: Universiti Teknologi Petronas

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.