Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I had a complete bipartite graph with edges each given some numerical "cost" value. Is there a way to select a subset of those edges such that each vertex on each side of the graph is mapped to each vertex on the other (one to one) and the total "costs" is maximized (or minimized)?

Has anyone ever formulated something equivalent to this?

share|improve this question
1  
Do you mean each vertex on on each side is mapped to a vertex on the other? (not each. The way you wrote it it looks like you're searching for a bi-clique). If that's the case, you should look at 'maximum weighted matching' which has a polynomial time algorithm. –  Or Zuk May 14 '11 at 11:56
    
Yes, I did mean "a" vertex on the other side, sorry for not being clear enough. And I shall look at that matching you've suggested, thanks very much! –  Glenn Habibi May 14 '11 at 12:25
add comment

2 Answers

up vote 1 down vote accepted

You are looking for the max-flow-min-cut theorem: http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

share|improve this answer
add comment

Looks like you are looking for maximum weighted bipartite matching - if so, see Wikipedia for initial pointers.

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.