Expected linear time MST algorithm: Difference between revisions

Revision as of 00:11, 25 December 2019

Revision as of 11:27, 18 February 2020

Line 48:

===F-heavy and F-light edges===

In each iteration the algorithm removes edges with particular properties that exclude them from the [[minimum spanning tree]]. These are called ''F-heavy edges'' and are defined as follows. Let ''F'' be a forest on the [[Graph (discrete mathematics)|graph]] ''H''. An F-heavy edge is an edge ''e'' connecting vertices ''u'',''v'' whose weight is strictly greater than the weight of the heaviest edge on the path from ''u'' to ''v'' in ''F''. (If a path does not exist in ''F'' it is considered to have infinite weight). Any edge that is not F-heavy is ''F-light''. If ''HF'' is a [[Glossary_of_graph_theory#Subgraphs|subgraph]] of ''G'' then any F-heavy edge in ''G'' cannot be in the minimum spanning tree of ''G'' by the [[Minimum_spanning_tree#Cycle_property|cycle property]]. Given a forest, F-heavy edges can be computed in [[linear time]] using a minimum spanning tree verification algorithm.<ref name=MST-V1/><ref name=MST-V2/>

==Algorithm==