Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

Question

Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$?

I read abstract of this paper that mentioned an algorithm with running time $O(n^2\log\log^*n)$. But i want know that, $O(n^2\log\log^*n)$ is lower bound or there is efficient algorithm that run in $O(n^2)$.

Answer 1

Yes, there are many such algorithms. Two of the easiest are

(1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each tree to a supervertex, and repeat. But modify it so that after the collapse you return to a simple graph rather than a multigraph. To do so, use radix sort to sort the edges by which pair of supervertices they connect, and then scan the sorted list to find blocks of edges connecting the same pair of supervertices and keep only the minimum-weight edge from each block. The time adds in a recurrence like $T(n)=O(n^2)+T(n/2)$ which solves to $O(n^2)$.

(2) Use Jarník's algorithm, where you build a tree one edge at a time using a priority queue of the remaining vertices outside of the tree, prioritized by the shortest edge connecting each vertex to the tree. Only instead of using anything as sophisticated as a binary heap for your priority queue, just use an unsorted collection of vertex-priority pairs. To find the minimum priority vertex, scan the collection in time $O(n)$. Then, when adding a vertex to the tree, look at all its neighboring edges and, for each neighbor that is not already in the tree, check whether the new connection to that neighbor is better than what you already had as its priority, and if so decrease the priority in its pair. There are $n$ scans with time $O(n)$, and $O(n^2)$ neighbor checks with time $O(1)$, so the total time is $O(n^2)$.

Randomization (which can achieve linear expected time for sparser graphs) is not needed here.