Design of New Mutation Operators for the Multi-Criteria Minimum Spanning Tree Problem

A spanning tree of an weighted, undirected and connected graph $G = (V, E, c)$ is a minimally connected subgraph $T = (V, E')$ of $G$. I.e., there is exactly one way between each pair of nodes in $T$. A spanning tree $T$ is termed minimal spanning tree (MST) if there is no spanning tree $T'$ of $G$ with lower sum of edge weights. The MST problem, i.e., finding a minimal spanning tree algorithmically, is a computationally easy problem. Famous algorithms, e.g., Prim's algorithm, find a MST in polynomial time. However, in real-world applications one is frequently confronted with intrinsically multi-objective problems with at least conflicting objectives which shall be minimized simultaneously. Hence, the multi-criteria minimum spanning tree problem (mcMST) is of utmost practical relevance.

In our work we analyse Pareto-optimal solutions of mcMST problems statistically and use the gained insights - as well as theoretical knowledge about the mcMST - to develop and evaluate a new mutation operator based on subtree replacement.

This accompanying website provides information on our ongoing and active project.


Contributed software

We wrapped our instance generation process and implementation of evolutionary multi-objective algorithms for the mcMST problem in a package for the statistical programming language R. Visit the public mcMST github repository for more in depth information.


We provide the problem instances generated for our benchmarks for reproducability: Download problem instances