Finding Minimum Spanning Trees

This paper studies methods for finding minimum spanning trees in graphs. Results include 1. several algorithms with O(mlog log n) worst-case running times, where n is the number vertices and m is the number of edges in the problem graph; 2. an $O(m)$ worst-case algorithm for dense graphs (those for which m is Ω (n1 + ε ) for some positive constant ε); 3. an $O(n)$ worst-case algorithm for planar graphs; 4. relationships with other problems which might lead general lower bound for the complexity of the minimum spanning tree problem.