Parallel algorithms for minimum spanning trees
In graph theory a minimum spanning tree (MST) T of a graph G = (V, E) with |V| = n and |E| = m is a tree subgraph of G that contains all of its vertices and is of minimum weight.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In graph theory a minimum spanning tree (MST) T of a graph G = (V, E) with |V| = n and |E| = m is a tree subgraph of 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 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 G , 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.…
In graph theory a minimum spanning tree (MST) T of a graph G = (V, E) with |V| = n and |E| = m is a tree subgraph of 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 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 G , 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 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), performance is a key factor.
One option of improving it is by parallelising known MST algorithms. pivot = chooseRandom( E ) (E_{\leq} , E_{>}) \gets partition( E , pivot) A \gets filterKruskal( E_{\leq} ) E_{>} \gets filter( E_{>} ) A \gets A \cup filterKruskal( E_{>} ) return A partition( E , pivot): E_{\leq} \gets \emptyset E_{>} \gets \emptyset foreach (u, v) \in E : if weight( u, v ) \leq pivot: E_{\leq} \gets E_{\leq} \cup {(u, v)} else E_{>} \gets E_{>} \cup {(u, v)} return ( E_{\leq} , E_{>} ) filter( E ): E_{filtered} \gets \emptyset foreach (u, v) \in E : if find-set(u) \neq find-set(v): E_{filtered} \gets E_{filtered} \cup {(u, v)} return E_{filtered} 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. This parallelisation utilises the adjacency array graph representation for G = (V, E) . This consists of three arrays - \Gamma of length n + 1 for the vertices, \gamma of length m for the endpoints of each of the m edges and c of length m for the edges' weights.
Now for vertex i the other end of each edge incident to i can be found in the entries between \gamma [\Gamma [i-1 and \gamma [\Gamma[i . The weight of the i -th edge in \Gamma can be found in c[i] . Then the i -th edge in \gamma is between vertices u and v if and only if \Gamma[u] \leq i and \gamma[i] = v . if \Gamma[v+1] = e v++ if c[e] pred[v] \gets e 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 prev 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 O(\log p) . Thus the total runtime of this step is in O(\frac{m}{p} + \log n + \log p) . if pred[w] = v \land v pred[v] \gets v 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: while \exists v \in V: pred[v] \neq pred[pred[v forAll v \in V pred[v] \gets pred[pred[v Now every subgraph is a star. With some advanced techniques this step needs O(\frac{n}{p} + \log n) time.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371174504 under CC BY-SA 4.0; modifications have been made.