A [[randomized algorithm]] for computing the [[minimum spanning forest]] of a [[weighted graph]] with no [[isolated vertex|isolated vertices]]. It was developed by [[David Karger]], Philip Klein, and [[Robert Tarjan]].<ref>{{Cite doijournal|doi=10.1145/201019.201022|title=A randomized linear-time algorithm to find minimum spanning trees|journal=Journal of the ACM|volume=42|issue=2|pages=321|year=1995|last1=Karger|first1=David R.|last2=Klein|first2=Philip N.|last3=Tarjan|first3=Robert E.}}</ref> The algorithm relies on techniques from [[Borůvka's algorithm]] along with an algorithm for verifying a minimum spanning tree in linear time.<ref name=MST-V1>{{Cite doijournal|doi=10.1137/0221070|title=Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time|journal=SIAM Journal on Computing|volume=21|issue=6|pages=1184|year=1992|last1=Dixon|first1=Brandon|last2=Rauch|first2=Monika|last3=Tarjan|first3=Robert E.}}</ref><ref name=MST-V2>{{cite conference
| last1 = King | first1 = Valerie | author1-link = Valerie King
| title = A Simpler Minimum Spanning Tree Verification Algorithm
