Parallel algorithms for minimum spanning trees
In graph theory a minimum spanning tree (MST) formula_1 of a graph formula_2 with formula_3 and formula_4 is a tree subgraph of formula_5 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 formula_5 is edge-unweighted every spanning tree possesses the same number of edges and thus the same weight. In the edge-weighted case, the spanning tree, the sum of the weights of the edges of which is lowest among all spanning trees of formula_5, is called a minimum spanning tree (MST). It is not necessarily unique. More generally, graphs that are not necessarily connected have minimum spanning forests, which consist of a union of MSTs for each  connected component. As finding MSTs is a widespread problem in graph theory, there exist many sequential algorithms for solving it. Among them are Prim's, Kruskal's and Borůvka's algorithms, each utilising different properties of MSTs. They all operate in a similar fashion - a subset of formula_8 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), performance is a key factor. One option of improving it is by parallelising known MST algorithms. Prim's algorithm. This algorithm utilises the cut-property of MSTs . A simple high-level pseudocode implementation is provided below: Each edge is observed exactly twice - namely when examining each of its endpoints. Each vertex is examined exactly once for a total of formula_19 operations aside from the selection of the lightest edge at each loop iteration. This selection is often performed using a priority queue (PQ). For each edge at most one decreaseKey operation (amortised in formula_20) is performed and each loop iteration performs one deleteMin operation (formula_21). Thus using Fibonacci heaps the total runtime of Prim's algorithm is asymptotically in formula_22. It is important to note that the  loop is inherently sequential and can not be properly parallelised. This is the case, since the lightest edge with one endpoint in formula_23 and on in formula_24 might change with the addition of edges to formula_1. Thus no two selections of a lightest edge can be performed at the same time. However, there do exist some attempts at parallelisation. One possible idea is to use formula_26 processors to support PQ access in formula_20 on an EREW-PRAM machine, thus lowering the total runtime to formula_19. Kruskal's algorithm. Kruskal's MST algorithm utilises the cycle property of MSTs. A high -level pseudocode representation is provided below. The subtrees of formula_1 are stored in union-find data structures, which is why checking whether or not two vertices are in the same subtree is possible in amortised formula_36 where formula_37 is the inverse Ackermann function. Thus the total runtime of the algorithm is in formula_38. Here formula_39 denotes the single-valued inverse Ackermann function, for which any realistic input yields an integer less than five. Approach 1: Parallelising the sorting step. Similarly to Prim's algorithm there are components in Kruskal's approach that can not be parallelised in its classical variant . For example, determining whether or not two vertices are in the same subtree is difficult to parallelise, as two union operations might attempt to join the same subtrees at the same time. Really the only opportunity for parallelisation lies in the sorting step. As sorting is linear in the optimal case on formula_21 processors, the total runtime can be reduced to formula_41. Approach 2: Filter-Kruskal. Another approach would be to modify the original algorithm by growing formula_1 more aggressively. This idea was presented by Osipov et al. The basic idea behind Filter-Kruskal is to partition the edges in  a similar way to quicksort and filter out edges that connect vertices that belong to the same tree in order to reduce the cost of sorting. A high-level pseudocode representation is provided below. Filter-Kruskal is better suited for parallelisation, since sorting, partitioning and filtering have intuitively easy parallelisations where the edges are simply divided between the cores. Borůvka's algorithm. The main idea behind Borůvka's algorithm is edge contraction. An edge formula_74 is contracted by first removing formula_32 from the graph and then redirecting every edge formula_76 to formula_77. These new edges retain their old edge weights . If the goal is not just to determine the weight of an MST but also which edges it comprises, it must be noted between which pairs of vertices an edge was contracted. A high-level pseudocode representation is presented below. It is possible that contractions lead to multiple edges between a pair of vertices. The intuitive way of choosing the lightest of them is not possible in formula_88. However, if all contractions that share a vertex are performed in parallel this is doable. The recursion stops when there is only a single vertex remaining, which means the algorithm needs at  most formula_89 iterations, leading to a total runtime in formula_90. Parallelisation. One possible parallelisation of this algorithm yields a polylogarithmic time complexity, i.e. formula_91 and there exists a constant formula_92 so that formula_93. Here formula_94 denotes the runtime for a graph with formula_95 edges, formula_96 vertices on a machine with formula_97 processors. The basic idea is the following: The MST then consists of all the found lightest edges. This parallelisation utilises the adjacency array graph representation for formula_2. This consists of three arrays - formula_103 of length formula_104 for the vertices, formula_105 of length formula_95 for the endpoints of each of  the formula_95 edges and formula_92 of length formula_95 for the edges' weights. Now for vertex formula_110 the other end of each edge incident to formula_110 can be found in the entries between formula_112 and formula_113. The weight of the formula_110-th edge in formula_103 can be found in formula_116. Then the formula_110-th edge in formula_105 is between vertices formula_31 and formula_32 if and only if formula_121 and formula_122. Finding the lightest incident edge. First the edges are distributed between each of the formula_97 processors. The formula_110-th processor receives the edges stored between formula_125 and formula_126. Furthermore, each processor  needs to know to which vertex these edges belong (since formula_105 only stores one of the edge's endpoints) and stores this in the array formula_128. Obtaining this information is possible in formula_21 using formula_97 binary searches or in formula_131 using a linear search. In practice the latter approach is sometimes quicker, even though it is asymptotically worse. Now each processor determines the lightest edge incident to each of its vertices. Here the issue arises some vertices are handled by more than one processor. A possible solution to this is that every processor has its own formula_140 array which is  later combined with those of the others using a reduction. Each processor has at most two vertices that are also handled by other processors and each reduction is in formula_141. Thus the total runtime of this step is in formula_99. Assigning subgraphs to vertices. Observe the graph that consists solely of edges collected in the previous step. These edges are directed away from the vertex to which they are the lightest incident edge. The resulting graph decomposes into multiple weakly connected components. The goal of this step is to assign to each vertex the component of which it is a  part. Note that every vertex has exactly one outgoing edge and therefore each component is a pseudotree - a tree with a single extra edge that runs in parallel to the lightest edge in the component but in the opposite direction. The following code mutates this extra edge into a loop: Now every weakly connected component is a directed tree where the root has a loop. This root is chosen as the representative of each component. The following code uses doubling to assign each vertex its representative: Now every subgraph is a star. With some advanced techniques this step needs formula_100  time. Contracting the subgraphs. In this step each subgraph is contracted to a single vertex. Finding the bijective function is possible in formula_156 using a prefix sum. As we now have a new set of vertices and edges the adjacency array must be rebuilt, which can be done using Integersort on formula_157 in formula_158 time. Complexity. Each iteration now needs formula_101 time and just like in the sequential case there are formula_89 iterations, resulting in a total runtime of formula_161. If formula_162 the efficiency of the algorithm is in formula_163 and it is relatively efficient. If formula_164 then it is  absolutely efficient. Further algorithms. There are multiple other parallel algorithms that deal the issue of finding an MST. With a linear number of processors it is possible to achieve this in formula_21. Bader and Cong presented an MST-algorithm, that was five times quicker on eight cores than an optimal sequential algorithm. Another challenge is the External Memory model - there is a proposed algorithm due to Dementiev et al. that is claimed to be only two to five times slower than an algorithm that only makes use of internal memory