Finding Minimum Spanning Trees in O(m alpha(m,n)) Time
Seth Pettie · 1999
We describe a deterministic minimum spanning tree algorithm running in time O(m alpha(m,n)), where alpha is a natural inverse of Ackermann''s function and m and n are the number of edges and vertices, respectively. This improves upon the O(m alpha(m,n) log alpha(m,n)) bound established by Chazelle in 1997. A similar O(m alpha(m,n))-time algorithm was discovered independently by Chazelle, predating the algorithm presented here by many months. This paper may still be of interest for its alternative exposition.