11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the worst case (a chain) you would remove exactly one edge per round, so you can't use that fact to improve bounds for a general graph. You could consider e.g. only complete graphs though. $\endgroup$ – Xodarap Jul 18 '12 at 19:26
  • $\begingroup$ @Xodarap if $G$ is a simple path (is that what you mean by chain?), then in the first round you select at least half the edges. These edges are removed from subsequent rounds. $\endgroup$ – Joe Jul 18 '12 at 19:37
  • $\begingroup$ Note that you can use one of the highly optimised union-find structures to improve this algorithm. $\endgroup$ – Raphael Jul 20 '12 at 16:01
5
$\begingroup$

It is possible to craft test cases for general graphs where your Borůvka's step wouldn't halve the number of edges in each step, even though it halves the number of vertices. An interesting note is that the optimization that you suggest works for planar graphs. This is because for planar graphs $|E| \leq 3*|V|-6 $ i,e $|E| = O(|V|)$. And in general it leads to a speed up for the class of minor closed families of graphs.

Reference:

  • Masters thesis, Claude Anderson (on page 100 the worst case input for Borůvka's algorithm is described). [link]

  • "Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320, 2004. [link]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.