Editing Minimum spanning tree (section)

=== Faster algorithms ===
Several researchers have tried to find more computationally-efficient algorithms.

In a comparison model, in which the only allowed operations on edge weights are pairwise comparisons, {{harvtxt|Karger|Klein|Tarjan|1995}} found a [[Expected linear time MST algorithm|linear time randomized algorithm]] based on a combination of Borůvka's algorithm and the reverse-delete algorithm.<ref>{{citation |last1=Karger |first1=David R. |title=A randomized linear-time algorithm to find minimum spanning trees |journal=[[Journal of the Association for Computing Machinery]] |volume=42 |issue=2 |pages=321–328 |year=1995 |doi=10.1145/201019.201022 |mr=1409738 |s2cid=832583 |last2=Klein |first2=Philip N. |last3=Tarjan |first3=Robert E. |author1-link=David Karger |author-link2=Philip N. Klein |author3-link=Robert Tarjan |doi-access=free}}</ref><ref>{{citation
 | last1 = Pettie | first1 = Seth
 | last2 = Ramachandran | first2 = Vijaya | author2-link = Vijaya Ramachandran
 | contribution = Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms
 | location = San Francisco, California
 | pages = 713–722
 | title = Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02)
 | contribution-url = http://portal.acm.org/citation.cfm?id=545477
 | year = 2002| isbn = 9780898715132
 }}.</ref>

The fastest non-randomized comparison-based algorithm with known complexity, by [[Bernard Chazelle]], is based on the [[soft heap]], an approximate priority queue.<ref name=Chazelle2000>{{citation
 | last = Chazelle | first = Bernard | author-link = Bernard Chazelle
 | doi = 10.1145/355541.355562
 | mr = 1866456
 | issue = 6
 | journal = [[Journal of the Association for Computing Machinery]]
 | pages = 1028–1047
 | title = A minimum spanning tree algorithm with inverse-Ackermann type complexity
 | volume = 47
 | year = 2000| s2cid = 6276962 | doi-access = free
 }}.</ref><ref>{{citation
 | last = Chazelle | first = Bernard | author-link = Bernard Chazelle
 | doi = 10.1145/355541.355554
 | mr = 1866455
 | issue = 6
 | journal = [[Journal of the Association for Computing Machinery]]
 | pages = 1012–1027
 | title = The soft heap: an approximate priority queue with optimal error rate
 | volume = 47
 | year = 2000| s2cid = 12556140| doi-access = free
 }}.</ref> Its running time is {{math|''[[Big O notation|O]]''(''m'' α(''m'',''n''))}}, where {{math|α}} is the classical functional [[Ackermann function#Inverse|inverse of the Ackermann function]]. The function {{math|α}} grows extremely slowly, so that for all practical purposes it may be considered a constant no greater than 4; thus Chazelle's algorithm takes very close to linear time.