Randomized Linear Time MST

linear time using randomization. Some of you will know all this.
There are two parts in this construction that are worth to be
known by all. I will present these (results by Karger, Klein
and Tarjan from J. ACM 42, and by King from Algorithmica 18).
The first is the proof that a random filtering technique is
very effective in reducing the number of edges that must be
considered: just as for connected components, where everything
is much easier, the full problem with n nodes and m edges
can be reduced to two problems with sqrt(n * m) edges. The
second nice idea (which has nothing to do with randomization)
is how to efficiently determine which edges are still candidates
for lying in a MST given a spanning tree T of a subset. Finally
i might consider whether all this is suitable for external memory
applications.