Towards a Resolution of the Minimum Spanning Tree Problem
It is tempting to consider Minimum Spanning Tree
a solved problem. Its randomized complexity is known,
and several fast, practical solutions exist.
And yet, one of the oldest questions in computer science
remains open: Is there a linear-time deterministic
algorithm for MST?
I will discuss recent progress on this question.
Specifically, I will sketch an algorithm
that is superlinear by a factor (roughly) equal
to the inverse of Ackermann's function.