3
$\begingroup$

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)$.

$\endgroup$
0
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I wasn't thinking straight when I made my earlier comment (which I removed to not confuse potential readers). In the dense graph regime algorithms that run in $O(m + n \log n)$ time become $O(m)$ when $m = \Omega(n \log n)$. One can do away with priority queues etc as David notes above if we only want $O(n^2)$. $\endgroup$ Oct 16 at 14:05
  • $\begingroup$ Amazing! ....... $\endgroup$
    – Jut
    Oct 18 at 0:17
  • $\begingroup$ What could be more elating to see - A teacher, an author of DS answering for DS! $\endgroup$ Oct 18 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.