1. Assume that all edge weights of the given connected undirected graph G (V, E) are...

Transcribed Image Text:

1. Assume that all edge weights of the given connected undirected graph G (V, E) are promised to be 1. Design the fastest algorithm you can to compute the minimum spanning tree (MST) of G. Argue the correctness of the algorithm and state its run-time. Your algorithm should be faster than the O(|E| log |V) run-time of Prim and Kruskal. - 2. Suppose instead that all edge weights are 1 except for a single edge eo = (uo, vo) whose weight is wo (note, wo might be either larger or smaller than 1). Show how to modify your solution in part 1 to compute the MST of G. What is the running time of your algorithm and how does it compare to the run-time you obtained in part 1 (or to standard Prim)? 1. Assume that all edge weights of the given connected undirected graph G (V, E) are promised to be 1. Design the fastest algorithm you can to compute the minimum spanning tree (MST) of G. Argue the correctness of the algorithm and state its run-time. Your algorithm should be faster than the O(|E| log |V) run-time of Prim and Kruskal. - 2. Suppose instead that all edge weights are 1 except for a single edge eo = (uo, vo) whose weight is wo (note, wo might be either larger or smaller than 1). Show how to modify your solution in part 1 to compute the MST of G. What is the running time of your algorithm and how does it compare to the run-time you obtained in part 1 (or to standard Prim)?