Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, the Fibonacci heap (or F-heap) supports arbitrary deletion in O(log n) amortized time and other heap operations in O(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containing n vertices and m edges, our minimum spanning tree algorithm runs in O(m log β (m, n)) time, improved from O(mβ(m, n)) time, where β(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs in O(n log n + m) time, improved from O(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex.