CS502 VU Current Assignment No. 5 Spring 2012 Solution

CS 502 Fundamental of Algorithms
Assignment # 05
Spring 2012
Total Marks = 20

Deadline
Your assignment must be uploaded / submitted before or on July 04, 2012

Question:

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?

Note:
To solve this question, you are requested to read Kruskal’s algorithm form your recommended book with listen the lecture carefully.