a Show that there is a graph such that Kruskals algorithm can find minimum spanning tree edges in the same order that Prims algorithm does b Let us consider Boruvka Sollins algorithm as shown in class Note that Boruvka Sollin algo rithm 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 Algorithm 1 One Step of Boruvka Sollins 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 G 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 (4a), we run Prims algorithm by calling MST PRIM(G, c, r), where G, with weight attribute c, is returned by the last phase and r is any vertex in G(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 Prims algo rithm without preprocessing

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Aug 28, 2024

a.Show that there is a graph such that Kruskals algorithm can find minimum spanning tree edges in the same order that Prims algorithm does. b.Let

a.Show that there is a graph such that Kruskals algorithm can find minimum spanning tree edges in the same order that Prims algorithm does.

b.Let us consider Boruvka/Sollins algorithm as shown in class. Note that Boruvka/Sollin algo- rithm 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.

Algorithm 1 One Step of Boruvka/Sollins 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 G 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 (4a), we run Prims algorithm by calling MST-PRIM(G, c, r), where G, with weight attribute c, is returned by the last phase and r is any vertex in G(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 Prims algo- rithm without preprocessing?