Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph

$\begingroup$

Suppose that we have a complete undirected positive weighted graph G={V,E} and I want to find one MST of it. My problem is what is the best (in time complexity) algorithm for it? The best prime complexity is O(V^2) The best Kruskal complexity is O(E.Log(E))=~O(V^2. Log(V)) any idea for lower time complexity?

$\endgroup$ 1

2 Answers

$\begingroup$

I believe there are deterministic linear time algorithms for sufficiently dense (such as complete) graphs.

One example is Prim's algorithm using a d-ary heap

See end of intro in

And another one using Fibonacci heaps:

Edit: Linear in the number of edges (i.e. quadratic in vertex number)

$\endgroup$ 1 $\begingroup$

I posted my question in computer science part and this is a resonable answer that I found:

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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