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.