Editing Minimum spanning tree (section)

==== 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.