Editing Minimum spanning tree (section)

=== Linear-time algorithms in special cases ===

==== Dense graphs ====

If the graph is dense (i.e. {{math|''m''/''n'' ≥ log log log ''n'')}}, then a deterministic algorithm by Fredman and Tarjan finds the MST in time {{math|O(''m'')}}.<ref>{{Cite journal | doi = 10.1145/28869.28874| title = Fibonacci heaps and their uses in improved network optimization algorithms| journal = Journal of the ACM| volume = 34| issue = 3| pages = 596| year = 1987| last1 = Fredman | first1 = M. L. | last2 = Tarjan | first2 = R. E. | s2cid = 7904683| doi-access = free}}</ref> The algorithm executes a number of phases. Each phase executes [[Prim's algorithm]] many times, each for a limited number of steps. The run-time of each phase is {{math|O(''m'' + ''n'')}}. If the number of vertices before a phase is {{mvar|n'}}, the number of vertices remaining after a phase is at most <math>\tfrac{n'}{2^{m/n'}}</math>. Hence, at most {{math|log*''n''}} phases are needed, which gives a linear run-time for dense graphs.<ref name=PettieRamachandran2002/>

There are other algorithms that work in linear time on dense graphs.<ref name=Chazelle2000/><ref>{{Cite journal | doi = 10.1007/bf02579168| title = Efficient algorithms for finding minimum spanning trees in undirected and directed graphs| journal = Combinatorica| volume = 6| issue = 2| pages = 109| year = 1986| last1 = Gabow | first1 = H. N. | author1-link = Harold N. Gabow | last2 = Galil | first2 = Z. | last3 = Spencer | first3 = T. | last4 = Tarjan | first4 = R. E. | s2cid = 35618095}}</ref>

==== Integer weights ====

If the edge weights are integers represented in binary, then deterministic algorithms are known that solve the problem in {{math|''O''(''m'' + ''n'')}} integer operations.<ref>{{citation
 | last1 = Fredman | first1 = M. L. | author1-link = Michael Fredman
 | last2 = Willard | first2 = D. E. | author2-link = Dan Willard
 | doi = 10.1016/S0022-0000(05)80064-9
 | mr = 1279413
 | issue = 3
 | journal = [[Journal of Computer and System Sciences]]
 | pages = 533–551
 | title = Trans-dichotomous algorithms for minimum spanning trees and shortest paths
 | volume = 48
 | year = 1994| doi-access = free
 }}.</ref>
Whether the problem can be solved ''deterministically'' for a ''general graph'' in ''linear time'' by a comparison-based algorithm remains an open question.