Authors: Matić, Dragan
Kratica, Jozef 
Maksimović, Zoran
Title: Solving the minimum edge-dilation k-center problem by genetic algorithms
Journal: Computers and Industrial Engineering
Volume: 113
First page: 282
Last page: 293
Issue Date: 1-Nov-2017
Rank: M21
ISSN: 0360-8352
DOI: 10.1016/j.cie.2017.09.029
In this paper, we present two genetic algorithms (GA) for solving the minimum edge-dilation k-center (MEDKC) problem. Up to now, MEDKC has been considered only theoretically, and we present the first heuristic approaches for solving it. In both approaches, the assignment of non-center vertices is based on the distance to the center vertices, while modified crossover and mutation genetic operators, specific for each GA, keep individuals feasible during the entire optimization process. The proposed algorithms were empirically tested and compared by using various sets of differently sized test data: some theoretical classes of graphs with known optimal solutions and some special classes of graphs chosen from the literature for the k-minimum spanning tree and Roman domination problems. Obtained results indicate that newly proposed GAs can be reliably used in constructing routing schemes in complex computer networks.
Keywords: Combinatorial optimization | Edge-dilation k center | Genetic algorithms | Minimum stretch
Publisher: Elsevier

Show full item record


checked on May 28, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.