Memetic Algorithm for the Minimum Edge Dominating Set Problem

Abdel-Rahman Hedar


The minimum edge dominating set (MEDS) is one of the fundamental covering problems ingraph theory, which finds many practical applications in diverse domains. In this paper, wepropose a meta-heuristic approach based on genetic algorithm and local search to solve theMEDS problem. Therefore, the proposed method is considered as a memetic search algorithmwhich is called Memetic Algorithm for minimum edge dominating set (MAMEDS). Inthe MAMEDS method, a new fitness function is invoked to effectively measure the solutionqualities. The search process in the proposed method uses intensification schemes besidethe main genetic search operations in order to achieve faster performance. The experimentalresults proves that the proposed method is promising in solving the MEDS problem.



Minimum edge dominating set, Graph theory, Genetic algorithm, Memetic Algorithm, Local search

Full Text:



  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

IAES International Journal of Artificial Intelligence (IJ-AI)
ISSN/e-ISSN 2089-4872/2252-8938 
This journal is published by the Institute of Advanced Engineering and Science (IAES) in collaboration with Intelektual Pustaka Media Utama (IPMU).

View IJAI Stats