For a very sparse connected graph G = (V, E), we can further improve upon the O(E + V lg V) running time of Prim's algorithm with Fibonacci heaps by preprocessing G to decrease the number of vertices before running Prim's algorithm. In particular, we choose, for each vertex u, the minimum-weight edge (u, ?) incident on u, and we put (u, ?) into the minimum spanning tree under construction. We then contract all chosen edges (see Section B.4). Rather than contracting these edges one at a time, we first identify sets of vertices that are united into the same new vertex. Then we create the graph that would have resulted from contracting these edges one at a time, but we do so by "renaming" edges according to the sets into which their endpoints were placed. Several edges from the original graph may be renamed the same as each other. In such a case, only one edge results, and its weight is the minimum of the weights of the corresponding original edges.

Initially, we set the minimum spanning tree T being constructed to be empty, and for each edge (u, ?) ? E, we initialize the attributes (u, ?).orig = (u, ?) and (u, ?). c = w(u, ?). We use the orig attribute to reference the edge from the initial graph that is associated with an edge in the contracted graph. The c attribute holds the weight of an edge, and as edges are contracted, we update it according to the above scheme for choosing edge weights. The procedure MST-REDUCE takes inputs G and T, and it returns a contracted graph G? with updated attributes orig? and c?. The procedure also accumulates edges of G into the minimum spanning tree T.

MST-REDUCE?(G, T)

a. Let T be the set of edges returned by MST-REDUCE, and let A be the minimum spanning tree of the graph G? formed by the call MST-PRIM (G?, c?, r), where c? is the weight attribute on the edges of G?.E and r is any vertex in G?.V. Prove that T ? {(x, y).orig? : (x, y) ? A} is a minimum spanning tree of G.

b. Argue that |G?. V| ? ?|V|/2.

c.?Show how to implement MST-REDUCE?so that it runs in?O(E)?time.

d. Suppose that we run k phases of MST-REDUCE, 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(k E).

e. Suppose that after running k phases of MST-REDUCE, as in part (d), we run Prim's 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.

f. For what values of |E| (in terms of |V|) does Prim's algorithm with preprocessing asymptotically beat Prim's algorithm without preprocessing?

Transcribed Image Text:

1 for each v e G.V 2 v.mark = FALSE 3 МАКE-SET(v) 4 for each u e G.V if u.mark == FA LSE choose v e G.Adj[u] such that (u, v).c is minimized UNION(u, V) T = T U {(u, v).orig} 7 8 u.mark = v.mark = TRUE 10 G'.V = {FIND-SEt(v) : v e G.V} 11 G'.E = Ø 12 for each (x, y) e G.E u = FIND-SET(x) v = FIND-SET (y) if (u, v) & G'.E G'.E = G'.E U {(u, v)} (u, v).orig' = (x, y).orig (и, v).c' %3D (х, у).c else if (x, у).c < (и, ).c' 13 14 15 16 17 18 19 20 21 22 construct adjacency lists G'.Adj for G' 23 return G' and T (u, v).orig' = (x, y).orig (и, v).c' —D (х, у).c