1
$\begingroup$

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:

  1. G' must include all the vertices of G.
  2. 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'.
  3. 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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Did you look in Schrijver's book on combinatorial optimization? $\endgroup$
    – Chandra Chekuri
    Oct 19, 2016 at 1:50
  • $\begingroup$ I don't have access to it without buying it, at the moment, but I've found a similar textbook I can get online for free through my University. I'll be reading through it later today. $\endgroup$
    – Nimrand
    Oct 19, 2016 at 2:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.