Please help me regarding following problem-Let us consider Boruvka/Sollin's algorithm . Note that Boruvka/Sollin algorithmselects several edges for inclusion in T at each stage. It terminates when onlyone tree at the end of a stage or no edges to be selected.Algorithm 1: One Step of Boruvka/Sollin'sAlgorithm1: Find minimum cost edge incident toevery 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 ofAlgorithm 1, using the output G0 produced by one phase as the input G to thenext phase and accumulating edges in T. Argue that the overall running time of thek phases is O(kE).(b) Suppose that after running k phasesof Algorithm 1, as in part (5a), we run Prim's algorithm by calling MST-PRIM (G0;c0; r), where G0, with weight attribute c0, is returned by the last phase and ris any vertex in G0(V). Show how to pick k so that the overall running time isO(E lg lg V ). Argue that your choice of k minimizes the overall asymptoticrunning time.(c) For what values of jEj (in terms ofjV j) does the above scheme asymptotically beat Prim's algorithm withoutpreprocessing?
Boruvka/Sollin's algorithm for MST
algorithms;graph theory;algorithm analysis;data structures