Real Analysis of MST Algorithms

Abstract

The Minimum Spanning Tree (MST) problem has a rich history dating back to the early 1920s. It is a cornerstone in the field of Algorithms and Combinatorial Optimization, having many uses such as network design and approximation of harder problems such as the Traveling Salesman Problem. Surprisingly, however, we still don't know the optimal time in which it can be computed. In this class, we will explore a greedy algorithm to compute the MST of a graph and see how it performs in different families of graphs. We will also see how to use these results to help you win in the board game "Ticket to Ride"!