5 (**) Parallelizable Prim\'s Given an undirected, weighted graph G(V, E), consi

Question

5 (**) Parallelizable Prim's Given an undirected, weighted graph G(V, E), consider the following algorithm to find the minimum spanning tree. This algorithm is similar to Prim's, except rather than grow out a spanning tree from one vertex, it tries to grow out the spanning tree from every vertex at the same time. procedure FindMST (G(V, E)) while T is not a spanning tree do Let S1, S2... Sk be the components of the graph with vertices V and edges T For each i, let ej be the minimum-weight edge with exactly one endpoint in S return T For simplicity, in the following parts you may assume that no two edges in G have the same weight. (a) Show that this algorithm finds a minimum spanning tree. (b) Give an exact upper bound (that is, an upper bound without using Big-O notation) on the worst-case number of iterations of the while loop in one run of the algorithm. (c) Using your answer to the previous part, give an upper bound on the runtime of this algorithm

Explanation / Answer

Answer:

a) We know the following theorem from CLRS

Theorem 23.1 Let G=(V,E) be a connected, undirected graph with a real-valued weight function w dened on E. Let A be a subset of E that is included in some minimum spanning tree for G, let.(S,V -S) be any cut of G that respects A, and let (u,v) be a light edge crossing .(S;V-S). Then, edge (u,v) is safe for A. (Note: Refer proof in the textbook)

Here, in the given algorithm, we start with a set of connected components and add the lightest edge crossing the component. Assuming the cut between the components, we see that it is safe to add the lightest edge to MST by above theorem. Hence, the algorithm adds only those edges those actually belong to MST and this shows the correctness of algorithm

b) In the worst case we may start with 'n' components which are the vertices themselves. Hence the following lemma holds

Lemma: The algorithm takes at most log n iterations to complete.

Proof At each step, we find the smallest edge leaving each connected component. Therefore, by the handshake lemma, the number of unique edges that we find at iteration i, is at least 1/2 ×zi where zi is the number of connected components at the beginning of iteration i. Therefore, at the end of iteration i, there are at most zi/2 connected components. If we had more than zi /2 unique edges, the number of connected components at the end of the iteration will only be fewer. At the beginning of the first iteration, each vertex is in its own connected component, z1 = n. Therefore, the number of unique edges added at the first iteration is at least n/2 . This means, that at the end of the end of the first iteration, there are at most n/2 connected components. Therefore, by induction, the number of connected components at the edge of iteration i is n/ (2^i ). When we are left with just 1 connected component, we have found the MST. Hence, the total number of iterations taken by the algorithm is log n.

c) We have already shown that the number of connected components at step i is at most n/(2^i) . The total processing time of the reduce operations can be expressed as the sum of a geometric series, nk /2 + nk/ 4 + nk /8 + ... + nk/ 2^ i = O (nk) The overall processing time for the union operations is the same as the processing time for the reduce operations since we assume that disjoint set operations take a constant amount of time. Therefore, the total processing time can be written as, log n {iterations }× O (m /k) {per iteration} + O(nk) {T otal cost of all the reduces}

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.