Parallel algorithms for minimum spanning trees

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> a <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> (MST) 
 
 
 
 T
 
 
 {\displaystyle T}
 
 of a <a href="/facts/Glossary_of_graph_theory_terms/W0MqKkyE">graph</a> 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
 with 
 
 
 
 
 |
 
 V
 
 |
 
 =
 n
 
 
 {\displaystyle |V|=n}
 
 and 
 
 
 
 
 |
 
 E
 
 |
 
 =
 m
 
 
 {\displaystyle |E|=m}
 
 is a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> <a href="/facts/Glossary_of_graph_theory_terms/W0MqKkyE">subgraph</a> of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 that contains all of its vertices and is of minimum weight. 
MSTs are useful and versatile tools utilised in a wide variety of practical and theoretical fields. For example, a company looking to supply multiple stores with a certain product from a single warehouse might use an MST originating at the warehouse to calculate the shortest paths to each company store. In this case the stores and the warehouse are represented as vertices and the road connections between them - as edges. Each edge is labelled with the length of the corresponding road connection.
If 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is <a href="/facts/Glossary_of_graph_theory_terms/W0MqKkyE">edge-unweighted</a> every spanning tree possesses the same number of edges and thus the same weight. In the <a href="/facts/Glossary_of_graph_theory_terms/W0MqKkyE">edge-weighted</a> case, the spanning tree, the sum of the weights of the edges of which is lowest among all spanning trees of 
 
 
 
 G
 
 
 {\displaystyle G}
 
, is called a <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> (MST). It is not necessarily unique. More generally, graphs that are not necessarily <a href="/facts/Glossary_of_graph_theory_terms/W0MqKkyE">connected</a> have minimum spanning <a href="/facts/Tree_(graph_theory)/TCWk4Joy">forests</a>, which consist of a <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a> of MSTs for each <a href="/facts/Connected_component_(graph_theory)/5owVSXtY">connected component</a>. 
As finding MSTs is a widespread problem in graph theory, there exist many <a href="/facts/Sequential_algorithm/Jl5SxP1U">sequential algorithms</a> for solving it. Among them are <a href="/facts/Prim%27s_algorithm/UHEcY2lH">Prim's</a>, <a href="/facts/Kruskal%27s_algorithm/sg8v1BHB">Kruskal's</a> and <a href="/facts/Bor%C5%AFvka%27s_algorithm/Hs1pkNRB">Borůvka's</a> algorithms, each utilising different properties of MSTs. They all operate in a similar fashion - a subset of 
 
 
 
 E
 
 
 {\displaystyle E}
 
 is iteratively grown until a valid MST has been discovered. However, as practical problems are often quite large (road networks sometimes have billions of edges), <a href="/facts/Time_complexity/77T62gmf">performance</a> is a key factor. One option of improving it is by <a href="/facts/Parallel_algorithm/nUPzEF4C">parallelising</a> known <a href="/facts/Minimum_spanning_tree/kgkGmY9s">MST algorithms</a>.

Parallel algorithms for minimum spanning trees open-in-new

Parallel algorithms for minimum spanning trees