1. An artificial bee colony algorithm for the minimum edge-dilation K-center problem.
- Author
-
Israni, Manisha and Sundar, Shyam
- Subjects
- *
POLYNOMIAL time algorithms , *GENETIC algorithms , *GRAPH connectivity , *UNDIRECTED graphs , *GENETIC variation , *BEES algorithm - Abstract
This paper studies the minimum edge-dilation K-center (MEDKC) problem for edge-weighted, undirected and connected graphs. This problem which is N P -hard holds significant relevance in designing efficient routing schemes for computer networks. To the best of our knowledge, there exists only two variants of genetic algorithm that have been developed for this problem. In this paper, we propose an artificial bee colony algorithm (ABC_MEDKC) for this problem. The proposed ABC_MEDKC incorporates two adaptable neighborhood operators specifically tailored for this problem in which the first neighborhood operator utilizes solution components of another solution, and the second neighborhood operator follows swapping of center vertices with non-center vertices in a mixed strategies of greedy and random approach. On available benchmark instances, computational results of ABC_MEDKC indicate that ABC_MEDKC overall outperforms the existing two variants of genetic algorithm in both solution quality and computational time. ABC_MEDKC also outperforms an existing polynomial-time approximation algorithm developed for this problem in terms of solution quality. ABC_MEDKC finds new values for 17 instances out of 91 instances. In addition, the convergence behavior of ABC_MEDKC and the statistical analysis are also studied. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF