The saga of minimum spanning trees

This article surveys the many facets of the Minimum Spanning Tree problem. We follow the history of the problem since the first polynomial-time solution by Bor˚uvka to the modern algorithms by Chazelle, Pettie and Ramachandran. We study the differences in time complexity dependent on the model of computation chosen and on the availability of random bits. We also briefly touch the dynamic maintenance of the MST and other related problems.