Editing Minimum spanning tree (section)

=== Parallel and distributed algorithms ===
{{further|Parallel algorithms for minimum spanning trees}}
Research has also considered [[parallel algorithm]]s for the minimum spanning tree problem.
With a linear number of processors it is possible to solve the problem in {{math|''O''(log ''n'')}} time.<ref>{{citation
 | last1 = Chong | first1 = Ka Wong
 | last2 = Han | first2 = Yijie
 | last3 = Lam | first3 = Tak Wah
 | doi = 10.1145/375827.375847
 | mr = 1868718
 | issue = 2
 | journal = [[Journal of the Association for Computing Machinery]]
 | pages = 297–323
 | title = Concurrent threads and optimal parallel minimum spanning trees algorithm
 | volume = 48
 | year = 2001| s2cid = 1778676
 }}.</ref><ref>{{citation
 | last1 = Pettie | first1 = Seth
 | last2 = Ramachandran | first2 = Vijaya
 | doi = 10.1137/S0097539700371065
 | mr = 1954882
 | issue = 6
 | journal = [[SIAM Journal on Computing]]
 | pages = 1879–1895
 | title = A randomized time-work optimal parallel algorithm for finding a minimum spanning forest
 | volume = 31
 | year = 2002| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf
 }}.</ref>

The problem can also be approached in a [[distributed computing|distributed manner]].  If each node is considered a computer and no node knows anything except its own connected links, one can still calculate the [[distributed minimum spanning tree]].