A randomized linear-time algorithm for finding minimum spanning trees
Philip N. Klein, Robert Endre Tarjan · 1994
We present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons. 1 Introduction We consider the problem of finding a minimum spanning tree in a connected graph with real-valued edge weights. This problem has a long and rich history; the first fully realized algorithm was devised by Boruvka in the 1920's [3]. An informative survey paper by Graham and Hell [9] describes the history of the problem up to 1985. In the last two decades faster and faster algorithms were found, the fastest being an algorithm of Gabow, Galil, and Spencer [7] (see also [8]), with a running time of O(m log fi(m; n)) on a ...