Deterministic linear-time minimum spanning tree
Can a minimum spanning tree be found deterministically in linear time by an algorithm that only compares edge weights?
Summary
Karger, Klein and Tarjan gave a randomised linear-time algorithm in 1995, and Bernard Chazelle’s deterministic algorithm runs in almost linear time, O(m α(m, n)). Pettie and Ramachandran found a provably optimal deterministic algorithm, but its running time is not known, so whether linear time is possible is open.
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.