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

- Two genetic algorithms (GA) for solving the minimum edge-dilation k-center (MEDKC) problem are proposed.
- Two different representation schemes are based on considering the distance to the central vertices.
- Specially designed genetic operators mutation and crossover keep individuals feasible.
- The proposed approaches are comprehensively tested on several classes of graphs.
- Obtained results demonstrate the efficacy of our proposed algorithms.

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.