Solving the minimum edge-dilation k-center problem by genetic algorithms

Abstract

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.