A minimum spanning tree algorithm with inverse-Ackermann type complexity

Reviewer: Paul Cull

An old chestnut has almost been shelled. Finding the minimum spanning tree is a basic problem which figures as an example in most graph and algorithm texts. The traditional algorithms have 0(E by E) run time. Usually a student will ask whether there is an 0(E) algorithm for this problem. The instructor usually says that no one has found such an algorithm and suggests that the student look at the improvements created by Yao and Tarjan. Now, Chazelle has come very close to 0(E) by producing an 0(\alpha E) algorithm where \alpha is the very very slowly growing inverse Ackermann function. This new algorithm is of the divide and conquer type and makes use of a new data structure the "soft heap." This new data structure is explained in a companion paper in the same issue. Finally, the bad news is that this algorithm is so complicated that it will probably never be implemented and will only be of theoretical interest. (Note: \alpha should be printed as the single Greek character.)