Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Expected linear time MST algorithm
open-in-new
<p>The expected linear time MST algorithm is a <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithm</a> for computing the <a href="/facts/Minimum_spanning_forest/kgkGmY9s">minimum spanning forest</a> of a <a href="/facts/Weighted_graph/W0MqKkyE">weighted graph</a> with no <a href="/facts/Isolated_vertex/WhlWmL3o">isolated vertices</a>. It was developed by <a href="/facts/David_Karger/mr17YBKD">David Karger</a>, Philip Klein, and <a href="/facts/Robert_Tarjan/kn1pMCN0">Robert Tarjan</a>. The algorithm relies on techniques from <a href="/facts/Bor%C5%AFvka%27s_algorithm/Hs1pkNRB">Borůvka's algorithm</a> along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of <a href="/facts/Divide_and_conquer_algorithms/pC1X7Ws7">divide and conquer algorithms</a>, <a href="/facts/Greedy_algorithms/alfsekco">greedy algorithms</a>, and <a href="/facts/Randomized_algorithms/Fngl1zgk">randomized algorithms</a> to achieve <a href="/facts/Expected_value/1XV0JKL8">expected</a> <a href="/facts/Linear_time/77T62gmf">linear performance</a>. </p><p>Deterministic algorithms that find the minimum spanning tree include <a href="/facts/Prim%27s_algorithm/UHEcY2lH">Prim's algorithm</a>, <a href="/facts/Kruskal%27s_algorithm/sg8v1BHB">Kruskal's algorithm</a>, <a href="/facts/Reverse-delete_algorithm/Psc5hj0h">reverse-delete algorithm</a>, and <a href="/facts/Bor%C5%AFvka%27s_algorithm/Hs1pkNRB">Borůvka's algorithm</a>. </p>