07-04-2012, 12:38 PM
Three Classic Greedy Algorithms
Borvuka.ppt (Size: 197.5 KB / Downloads: 34)
Problem Definition
Input
Weighted, connected undirected graph G=(V,E)
Weight (length) function w on each edge e in E
Task
Compute a spanning tree of G of minimum total weight
Spanning tree
If there are n nodes in G, a spanning tree consists of n-1 edges such that no cycles are formed
Property of MST’s
Cycle Property: For any cycle C in a graph, the heaviest edge in C does not appear in the minimum spanning tree
Boruvka’s Algorithm
Prim “in parallel”
Boruvka Step:
We have a graph of vertices
For each v in V, select the minimum weight edge connected to v
Update
Contract all selected edges, replacing each connected component by a single vertex
Delete loops, and keep only the lowest weight edge in a multi-edge
Run Boruvka steps until we have a single node
Boruvka’s Algorithm Analysis
RUNTIME:
Borůvka's algorithm can be shown to run in time O(m log n), where m is the number of edges, and n is the number of vertices.
Correctness:
How can we verify that each edge we add is part of an MST?
Verification Algorithm
For each edge (u,v) not in T, find T(u,v).
Compare w (u,v) to w(T(u,v))
If all are ok, then return yes, else return no.
Running time?
O(E) time to perform comparisons
Sophisticated techniques to find all the T(u,v) in O(E) time.