Question

Let us consider Boruvka/Sollin's algorithm as shown . Note that Boruvka/Sollin algorithm selects several edges for inclusion in T at each stage. It terminates when only one tree at the end of a stage or no edges to be selected.

One Step of Boruvka/Sollin's Algorithm

1: Find minimum cost edge incident to every vertex.

2: Add to tree T.

3: Remove cycle if any.

4: Compress and clean graph (eliminate multiple edges).

(a) Suppose that we run k phases of Algorithm 1, using the output G0 produced by one phase as the input G to the next phase and accumulating edges in T. Argue that the overall running time of the k phases is O(kE).

(b) Suppose that after running k phases of Algorithm 1, as in part (5a), we run Prim's algorithm (normal Prim's algo) by calling MST-PRIM (G0; c0; r), where G0, with weight attribute c0, is returned by the last phase and r is any vertex in G0(V). Show how to pick k so that the overall running time is O(E lg lg V ). Argue that your choice of k minimizes the overall asymptotic running time.

(c) For what values of |E| (in terms of |V |) does the above scheme asymptotically beat Prim's algorithm without preprocessing?

Answer 1