Expected linear time MST algorithm: Difference between revisions

Revision as of 09:25, 16 April 2012

Revision as of 09:26, 16 April 2012

Line 80:

1 If ''G'' is empty return an empty forest

2 Create a contracted graph ''G''' by running two successive Borůvka steps on ''G''

3 Create a subgraph ''H'' by selecting each edge in ''G''' with probability 1/2. Recursively apply the algorithm to ''H'' to get theits minimum spanning forest ''F'' of ''H''.

4 Remove all F-heavy edges from ''G''' (where ''F'' is the forest from step 3) using a [[MST verification algorithm|linear time minimum spanning tree verification algorithm]]<ref name=MST-V1/><ref name=MST-V2/>.

5 Recursively apply the algorithm to ''G''' to get its minimum spanning forest.

Output: The minimum spanning forest of ''G''' and the contracted edges from the Borůvka steps

==Correctness==