Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints:
- G' must include all the vertices of G.
- All vertices must be connected to at least one vertex of G'. In other words the edges of G' must cover all the vertices of G'.
- The total weights of all edges in G' must be as low as possible.
In other words, this is the minimum weighted edge cover problem.
So, my question is, in terms of time complexity with respect to the number of vertices and edges, what is the fastest known algorithm for finding the correct answer?
What I've done so far:
I've found some resources online, but they often seem to say contradictory things.
I was able to find one post that pointed out that this problem can be reformulated as a maximum matching problem (see here).
In that case, I've found references to Edmond's Algorithm, which can run in O(V^2*E) or O(V^3) time. There are references to improved versions of this algorithm, but as far as I can tell, these only deal with unweighted graphs, not weighted ones. So, as far as the known solutions go, is O(V^2*E) or O(V^3) time complexity the best we can get?