On Minimum Spanning Trees

The minimal spanning tree problem is one of the oldest and most basic graph problems in theoretical computer science. Its history dates back to Boruvka's algorithm in 1926 and till today it is a extensively researched problem with new breakthroughs only recently. Given an edge-weighted graph, this problem calls for nding a subtree spanning all the vertices, whose total weight isminimal. The central open question is: Does there exist a linear time deterministic algorithm that finds the minimal spanning tree? This problem remains open. We will present the problem from different angles giving our insight on each. We present the problem in a new framework, and improve the running time for specific families of graphs in this framework