Content deleted Content added
Line 20:
Two commonly used algorithms for the classical minimum spanning tree problem are [[Prim's algorithm|Prim’s algorithm]] and [[Kruskal's algorithm|Kruskal’s algorithm]]. However, it is difficult to apply these two algorithms in the distributed message-passing model. The main challenges are:
* Both [[Prim's algorithm|Prim’s algorithm]] and [[Kruskal's algorithm|Kruskal’s algorithm]] require processing one node or vertex at a time, making it difficult to make them run in parallel. (For example, Kruskal's algorithm processes edges in turn, deciding whether to include the edge in the MST based on whether it would form a cycle with all previously chosen edges.)
* Both [[Prim's algorithm|Prim’s algorithm]] and [[Kruskal's algorithm|Kruskal’s algorithm]] require processes to know the state of the whole graph, which is very difficult to discover in the message-passing model.
However, Nobari ''et al.'' in <ref name=nobari2012>{{citation | last1 = Nobari | first1 = Sadegh | author1-link = Sadegh Nobari
| last2 = Cao | first2 = Thanh-Tung
| |||