# 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.

## People

## 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.

## Data

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

Download problem instances