Competition between Dandelion and Prüfer encoded genetic algorithms for solving the clustered minimum routing tree problem
Cosmin Sabo, Petrică C. Pop, Bogdan Teglaș, Adrian Petrovan

Abstract. The Clustered Minimum Routing Tree Problem (CluMRTP) is a challenging extension of the classical Minimum Routing Tree Problem in which the vertices of a graph are partitioned into clusters, and the objective is to find a minimum-cost routing tree such that each cluster forms a connected subgraph. This paper sets up a computational competition between two powerful tree-encoding strategies inside genetic algorithms: Dandelion-encoded and Prüfer-encoded representations. Each encoding is used to drive a hybrid genetic algorithm that combines macro-level evolution of the inter-cluster tree with local-level construction of intra-cluster connectivity. Through extensive experiments on benchmark instances, the relative strengths and weaknesses of the two encodings are analysed in terms of solution quality, convergence behaviour and robustness. The results provide concrete guidance for the choice of tree encoding when designing evolutionary algorithms for the CluMRTP and related network design problems.

Keywords: clustered minimum routing tree problem; genetic algorithms; Dandelion encoding; Prüfer encoding; combinatorial optimization

Cosmin Sabo, Petrică C. Pop, Bogdan Teglaș, Adrian Petrovan, "Competition between Dandelion and Prüfer encoded genetic algorithms for solving the clustered minimum routing tree problem", Carpathian Journal of Mathematics, vol. 41, no. 4, 2025, pp. 1045–1059, 2023. DOI: https://doi.org/10.37193/CJM.2025.04.13.

Reference: Carpathian Journal of Mathematics, vol. 41, no. 4, 2025, pp. 1045–1059. DOI: 10.37193/CJM.2025.04.13

Other publications