Given a connected, undirected graph whose edges are labelled, the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours). This problem has many real-life applications such as communication networks where each node can communicate via different types of channels. In this project, you will investigate various methods for solving the MLST problem. The project required background in probability theory and C++ programming skills.

Project members

Supervisor: Slava Vaisman

Dr Slava Vaisman