0
$\begingroup$

Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$?

The best prime complexity I have found is $O(|V|^2)$, and the complexity of the Kruskal algorithm is $O(|E|\cdot \log(|E|))= O(|V|^2 \cdot \log(|V|))$.

Any ideas for how to improve the time complexity so that we get something more efficient than $|V|^2$?

$\endgroup$
0
$\begingroup$

Since it is a complete undirected graph, the number of edges are $\Theta(n^{2})$, where $n = |V|$. In order to find the MST, you must find the edge of minimum weight among all the given edges since it is always a part of the Minimum Spanning Tree. Since, the lower bound of finding the minimum among $N$ elements is $\Omega(N)$. Therefore, you can not do better than $\Omega(n^{2})$ if the graph is complete.

$\endgroup$
1
  • $\begingroup$ Thanks, It seems to be correct. $\endgroup$ – hossein torki Dec 26 '20 at 11:31

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.