CS502 Assignment No 5 Solution Spring 2012

 CS502 Assignment No 5 Solution Spring 2012

Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

Solution:
We know that Kruskal’s algorithm takes O(V ) time for initialization, O(E lgE) time to sort
the edges, and O(E(V )) time for the disjoint-set operations, for a total running time of O(V +
E lgE + E(V )) = O(E lgE).
If we knew that all of the edge weights in the graph were integers in the range from 1 to |V |,
then we could sort the edges in O(V + E) time using counting sort. Since the graph is connected,
V = O(E), and so the sorting time is reduced to O(E). This would yield a total running time of
O(V + E + E(V )) = O(E(V )), again since V = O(E), and since E = O(E(V )). The time
to process the edges, not the time to sort them, is now the dominant term. Knowledge about the
weights won’t help speed up any other part of the algorithm, since nothing besides the sort uses
the weight values.
If the edge weights were integers in the range from 1 to W for some constant W, then we could again
use counting sort to sort the edges more quickly. This time, sorting would take O(E +W) = O(E)
time, since W is a constant. As in the first part, we get a total running time of O(E(V )).