Parallel algorithms for minimum spanning trees: Difference between revisions

Revision as of 15:20, 29 July 2025

Latest revision as of 05:49, 3 August 2025

(One intermediate revision by one other user not shown)

Line 6:

If <math>G</math> is [[Glossary_of_graph_theory_terms#unweighted_graph|edge-unweighted]] every spanning tree possesses the same number of edges and thus the same weight. In the [[Glossary_of_graph_theory_terms#weighted_graph|edge-weighted]] case, the spanning tree, the sum of the weights of the edges of which is lowest among all spanning trees of <math>G</math>, is called a [[minimum spanning tree]] (MST). It is not necessarily unique. More generally, graphs that are not necessarily [[Glossary_of_graph_theory_terms#connected|connected]] have minimum spanning [[Tree_(graph_theory)#Forest|forests]], which consist of a [[Union_(set_theory)|union]] of MSTs for each [[Connected_component_(graph_theory)|connected component]].

As finding MSTs is a widespread problem in graph theory, there exist many [[Sequential_algorithm|sequential algorithms]] for solving it. Among them are [[Prim's algorithm|Prim's]], [[Kruskal's algorithm|Kruskal's]] and [[Borůvka's algorithm|Borůvka's]] algorithms, each utilising different properties of MSTs. They all operate in a similar fashion - a subset of <math>E</math> is iteratively grown until a valid MST has been determineddiscovered. However, as practical problems are often quite large (road networks sometimes have billions of edges), [[Time_complexity|performance]] is a key factor. One option of improving it is by [[Parallel algorithm|parallelising]] known [[Minimum_spanning_tree#Algorithms|MST algorithms]].<ref>{{cite book |last1=Sanders |last2=Dietzfelbinger |last3=Martin |last4=Mehlhorn |last5=Kurt |last6=Peter |title=Algorithmen und Datenstrukturen Die Grundwerkzeuge |publisher=Springer Vieweg |isbn=978-3-642-05472-3|date=2014-06-10 }}</ref>

== Prim's algorithm ==

Line 220:

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<ref>{{citation

| last1 = Dementiev
| first1 = Roman

| last2 = Sanders
| first2 = Peter

| last3 = Schultes
| first3 = Dominik

| last4 = Sibeyn
| first4 = Jop F.

| contribution = Engineering an external memory minimum spanning tree algorithm

| pages = 195–208

| title = Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004)

| url = http://algo2.iti.kit.edu/dementiev/files/emst.pdf

| year = 2004}}.</ref>

| access-date = 2019-05-24

| archive-date = 2011-08-09

| archive-url = https://web.archive.org/web/20110809075049/http://algo2.iti.kit.edu/dementiev/files/emst.pdf

| url-status = dead

}}.</ref>

== References ==