Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
add comment

migrated from math.stackexchange.com Aug 17 '12 at 16:48

This question came from our site for people studying math at any level and professionals in related fields.

1 Answer

But it seems to work anyway:

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

Mathematica graphics

Verification:

WeightedAdjacencyMatrix[g] // MatrixForm

Mathematica graphics

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.