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

Question

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?

Answer 1

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

Answer 2

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 https://en.wikipedia.org/wiki/Prim%27s_algorithm

And another one using Fibonacci heaps: https://dl.acm.org/doi/10.1145/28869.28874

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