Expected linear time MST algorithm: Difference between revisions

Revision as of 05:24, 22 April 2012

Revision as of 12:03, 21 May 2012

Line 101:

Ignoring work done in recursive subproblems the total amount of work done in a single invocation of the algorithm is [[linear time|linear]] in the number of edges in the input graph. Step 1 takes constant time. Borůvka steps can be executed in time linear in the number of edges as mentioned in the [[#Borůvka steps|Borůvka step]] section. Step 3 iterates through the edges and flips a single coin for each one so it is linear in the number of edges. Step 4 can be executed in linear time using a modified [[MST verification algorithm|linear time minimum spanning tree verification algorithm]].<ref name=MST-V1/><ref name=MST-V2/> Since the work done in one iteration of the algorithm is linear in the number of edges the work done in one complete run of the algorithm (including all recursive calls) is bounded by a constant factor times the total number of edges in the original problem and all recursive subproblems.

Each invocation of the algorithm produces at most two subproblems so the set of subproblems forms a [[binary tree]]. Each [[#Borůvka steps|Borůvka step]] reduces the number of vertices by at least a factor of two so after two Borůvka steps the number of vertices has been reduced by a factor of four. Thus, if the original graph has ''n'' vertices and ''m'' edges then at depth ''d'' of the the tree each subproblem is on a graph of at most ''n''/4^''d'' vertices. Also the tree has at most log₄''n'' levels.

[[File:Linear MST Algorithm Left Subchildren.svg|thumb|right|Left paths of a binary tree are circled in blue]]