Deterministic Linear-Time Minimum Spanning Tree Problem
Determine whether there exists a uniform deterministic comparison-based algorithm that, for every connected undirected graph with n vertices and m edges carrying distinct real-valued weights, computes a minimum spanning tree in worst-case O(m) time on a pointer machine, with edge weights accessed only by binary comparisons, in the model of Pettie and Ramachandran (2002).
Status Open Status review date not recorded in this edition
Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.