2008.12.03 | Gerth Stølting Brodal

This thesis describes the optimal minimum spanning tree algorithm given by Pettie
and Ramachandran (in Journal of the ACM, 2002). The algorithm presented finds a
minimum spanning tree of a graph with n vertices and m edges deterministically in time
O (T* (m, n)), where T* is the minimum number of edge-weight comparisons needed to
determine the solution of the problem. The function T* is the decision tree complexity of
the minimum spanning tree problem, and thus the algorithm shows that the algorithmic
complexity of the problem is equal to its decision tree complexity.
Even though the algorithm runs in optimal time, the exact function describing the running
time is not known at present, and is thus still an open problem. A trivial lower bound is
T*(m, n) = Omega(m). A deterministic upper bound is T*(m, n) = O (m · a(m, n)), due to
Chazelle (in Journal of the ACM, 2000). Here, a is the very slow growing inverse of the
Ackermann function.
The optimal algorithm uses hardwired optimal decision trees for very small graphs
compared to the input graph, but for input graph instances with practical size, the decision
trees are not required to obtain the optimal running time. Because the optimal algorithm is
relatively advanced, the hidden Big-Ohconstant of its running time is relatively large. This
thesis implements the optimal algorithm, except for the decision trees, and compares its
running time with minimum spanning tree algorithms with theoretically higher complexity.
The result of the experiments show that some of these algorithms are significantly faster
than the optimal algorithm for practical input graph instances. The overall experiment
winner is the algorithm originally discovered by Jarnik, and later by Prim and Dijkstra,
which in all experiments is significantly faster than the optimal algorithm. However, the
experiments show that for a special graph family, the optimal algorithm is faster than the
earliest minimum spanning tree algorithm known, namely Boruvka’s algorithm.
Consequently, for practical purposes, the algorithm described provides no benefit to the
solution of the minimum spanning tree problem.