Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Memetic Algorithm for the Minimum Edge Dominating Set Problem

Abdulaziz, Shada LU ; Hedar, Abdel-Rahman and Sewisy, Adel (2013) In International Journal of Artificial Intelligence 2(4). p.179-186
Abstract
The minimum edge dominating set (MEDS) is one of the fundamental covering problems in graph theory, which finds many practical applications in diverse domains. In this paper, we propose a meta-heuristic approach based on genetic algorithm and local search to solve the MEDS problem. Therefore, the proposed method is considered as a memetic search algorithm which is called Memetic Algorithm for minimum edge dominating set (MAMEDS). In the MAMEDS method, a new fitness function is invoked to effectively measure the solution qualities. The search process in the proposed method uses intensification schemes beside the main genetic search operations in order to achieve faster performance. The experimental results proves that the proposed method is... (More)
The minimum edge dominating set (MEDS) is one of the fundamental covering problems in graph theory, which finds many practical applications in diverse domains. In this paper, we propose a meta-heuristic approach based on genetic algorithm and local search to solve the MEDS problem. Therefore, the proposed method is considered as a memetic search algorithm which is called Memetic Algorithm for minimum edge dominating set (MAMEDS). In the MAMEDS method, a new fitness function is invoked to effectively measure the solution qualities. The search process in the proposed method uses intensification schemes beside the main genetic search operations in order to achieve faster performance. The experimental results proves that the proposed method is promising in solving the MEDS problem. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Minimum edge dominating set, Graph theory, Genetic algorithm, Memetic Algorithm, Local search
in
International Journal of Artificial Intelligence
volume
2
issue
4
pages
8 pages
publisher
Centre for Environment, Social and Economic Research Publications
DOI
10.11591/ij-ai.v2i4.3481
language
English
LU publication?
yes
id
34133c03-172e-4bb4-80f5-7c97bd5ba23b
date added to LUP
2019-09-27 12:50:14
date last changed
2019-09-27 15:14:56
@article{34133c03-172e-4bb4-80f5-7c97bd5ba23b,
  abstract     = {{The minimum edge dominating set (MEDS) is one of the fundamental covering problems in graph theory, which finds many practical applications in diverse domains. In this paper, we propose a meta-heuristic approach based on genetic algorithm and local search to solve the MEDS problem. Therefore, the proposed method is considered as a memetic search algorithm which is called Memetic Algorithm for minimum edge dominating set (MAMEDS). In the MAMEDS method, a new fitness function is invoked to effectively measure the solution qualities. The search process in the proposed method uses intensification schemes beside the main genetic search operations in order to achieve faster performance. The experimental results proves that the proposed method is promising in solving the MEDS problem.}},
  author       = {{Abdulaziz, Shada and Hedar, Abdel-Rahman and Sewisy, Adel}},
  keywords     = {{Minimum edge dominating set; Graph theory; Genetic algorithm; Memetic Algorithm; Local search}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{179--186}},
  publisher    = {{Centre for Environment, Social and Economic Research Publications}},
  series       = {{International Journal of Artificial Intelligence}},
  title        = {{Memetic Algorithm for the Minimum Edge Dominating Set Problem}},
  url          = {{http://dx.doi.org/10.11591/ij-ai.v2i4.3481}},
  doi          = {{10.11591/ij-ai.v2i4.3481}},
  volume       = {{2}},
  year         = {{2013}},
}