# How do I find a weighted bipartite graph's minimum edge cover using Mathematica 8?

In graph theory, we use the Hungarian Algorithm to compute a weighted bipartite graph's minimum edge cover (a set of edges that is incident to every vertices, the one with the minimum total weight.)

I find that in new version 8 of Mathematica, there is a whole new package of functions for Graph Theory, (begin with Graph[].) But I've not found any function that do this job. I do find a function called FindEdgeCover[] that can only find a edge cover, not the minimum one.

But it seems to work anyway:

g = CompleteGraph[5, EdgeWeight -> Range@10, EdgeLabels -> "Name"];
g1 = CompleteGraph[5];
HighlightGraph[#, FindEdgeCover[#], ImagePadding -> 10] & /@ {g, g1}


Verification:

WeightedAdjacencyMatrix[g] // MatrixForm


W = CompleteGraph[5, EdgeWeight -> Range@10, EdgeLabels -> "Name"];

• This is not an answer to the question. Nov 12 at 2:44