Suggested Final Project Topics

Pettie and Ramachandran's Optimal MST Algorithm

The minimum spanning tree problem is one of the longest-studied combinatorial optimization problems.

In   CS161,   you   saw   Prim's   and   Kruskal's   algorithms   for   finding   MSTs,   and   may   have   come   across

Borůvka's algorithm as well. Since then, a number of algorithms have been proposed for solving MST. In

2002, Pettie and Ramachandran announced a major discovery – they had developed an MST algorithm

that was within a constant factor of the optimal MST algorithm! There's one catch, though: no one knows

how fast it is!