History of MST

Read the following article by Graham and Hell on the history of algorithms for the minimum spanning tree (MST) problem: go here and click the PDF link.

(If you have problems with the link, just search Google for "Graham Hell History Minimum Spanning Tree Problem" or somthing like that.)

The article mentions many different MST algorithms. In your write-up, I want you to discuss ones that you think are most interesting. Feel free to give some small examples to show how they work. What problems in real life motivated people to study these algorithms?

This article was written in 1985, a full 10 years before the randomized MST algorithm that we saw in class. Discuss the impact of Karger, Klein, and Tarjan's randomized algorithm on the state of MST computation. Do you think it makes a bigger difference in theory or in practice? Why? How might the last section of the article look if it were written today? (You might want to do a little extra outside research.)

I expect 2-3 pages worth of summary, hopefully with a good example diagram or two. (Please don't insult your professor by thinking he will be tricked by wide margins, big spacing, large fonts, huge titles, and all those tricks we learned in middle school.)