Content deleted Content added
Remove self-promotional uncited literature spam. |
Modified with the state-of-the-art approach for fining MSF. |
||
Line 22:
* 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
| last3 = Karras| first3 = Panagiotis
| last4 = Bressan| first4 = Stéphane
| doi = 10.1145/2145816.2145842
| issue = 11
| journal = Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming
| pages = 205–214
| title = Scalable parallel minimum spanning forest computation
| url = http://dl.acm.org/citation.cfm?id=2145816.2145842
| ___location = New Orleans, Louisiana, USA
| publisher = ACM
| isbn = 978-1-4503-1160-1
| year = 2012}}.</ref> proposed a novel solution by parallelizing [[Prim's algorithm|Prim’s algorithm]]. In their approach they execute Prim's algorithm starting from different nodes concurrently and let each sub-graph to grow as much as it is allowed. Finally, merging the created sub-graphs as the result.
Due to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model. Some bear similarities to [[Borůvka's algorithm]] for the classical MST problem.
| |||