Welcome to MathOverflow

Question

1

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?

flag	asked May 14 2011 at 11:46 Glenn Habibi 33●2

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 2011 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 2011 at 12:25

Per Alexandersson · Accepted Answer · 2011-05-14 14:56:57Z UTC

1

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

answered May 14 2011 at 14:56

Per Alexandersson
1,761●6●12

Max Alekseyev · Answer 2 · 2011-05-14 14:27:26Z UTC

1

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

answered May 14 2011 at 14:27

Max Alekseyev
1,669●4●9

“Bipartite” Travelling Salesman Problem?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.