Recap

Start with a weighted graph G=(V,E,w).

Want to select a subset of edges that interconnect all nodes with the smallest possible total weight.

The ``greedy-grow lemma'' is our main theoretical tool for analyzing algorithms for solving this problem.


next up previous
Next: Algorithm Up: KRUSKAL'S ALGORITHM Previous: KRUSKAL'S ALGORITHM