Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.
The pseudo-code is:
MST T = empty tree
Begin with each vertex as a component
While number of components > 1
For each component c
let e = minimum edge out of component c
if e is not in T
add e to T //merging the two components connected by e
We call each iteration of the outer loop a round. In each round, the inner loop cuts the number of components at least in half. Therefore there are at most $O(\log n)$ rounds. In each round, the inner loop looks at each edge at most twice (once from each component). Therefore the running time is at most $O(m \log n)$.
Now suppose after each round, we remove all the edges which only connect vertices within the same component and also remove duplicate edges between components, so that the inner loop only looks at some number of edges m' < m which are the minimum weight edges which connect two previously disconnected components.
How does this optimization affect the running time?
If we somehow knew that in each round, it would cut the number of edges in half, then the running time would be significantly improved: $T(m) = T(m /2) + O(m) = O(m)$.
However, while the optimization will dramatically reduce the number of edges examined, (only 1 edge by the final round, and at most # of components choose 2 in general), it's not clear how/if we can use this fact to tighten the analysis of the run-time.
