Bernard Chazelle

Princeton University

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.