Algorithm for finding MST in linear time

Question

Are there any algorithm for finding MST of given graph $G$ in linear time?

I found this paper at this link But I can't understand it running time is linear or not.

• D.W.: cs.stackexchange.com/q/84686/755, cs.stackexchange.com/q/145124/755

Answer 1

To the best of my knowledge, the best algorithm for computing a minimum spanning tree runs in time $O(m \alpha(m,n))$, where $n$ is the number of vertices, $m$ is the number of edges, and $\alpha$ is the inverse Ackermann function. See Rahul Simha's page on MST for a description of the algorithm and references to the literature.

What Pettie and Ramachandran showed in the paper you link to is that there is no gap between the query complexity of the MST problem and its computational complexity. That is, if there is a decision tree making $X$ comparisons in the worst case, then they can convert it into an algorithm running in time $O(X)$. Compare this to the situation for 3SUM, where the query complexity is $\tilde{O}(n)$, while the computational complexity is conjectured to be $\tilde\Omega(n^2)$.