A minimum spanning tree algorithm with Inverse Ackermann type complexity
A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m alpha (m, n)), where alpha is the classical functional inverse of Ackermann's function and n (respectively, in) is the number of vertices (respectively, edges). The algorithm is comparison-based: it uses pointers, not arrays, and it makes no numeric assumptions on the edge costs.
minimum spanning trees graphs theory matroids