Papex

Open problem · Computer science · Open

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.

More in Computing