"Bipartite" Travelling Salesman Problem? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:13:07Z http://mathoverflow.net/feeds/question/64977 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64977/bipartite-travelling-salesman-problem "Bipartite" Travelling Salesman Problem? Glenn Habibi 2011-05-14T11:46:28Z 2011-05-14T14:56:57Z <p>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)?</p> <p>Has anyone ever formulated something equivalent to this?</p> http://mathoverflow.net/questions/64977/bipartite-travelling-salesman-problem/64987#64987 Answer by Max Alekseyev for "Bipartite" Travelling Salesman Problem? Max Alekseyev 2011-05-14T14:27:26Z 2011-05-14T14:27:26Z <p>Looks like you are looking for maximum weighted bipartite matching - if so, see <a href="http://en.wikipedia.org/wiki/Maximal_matching#Maximum_matchings_in_bipartite_graphs" rel="nofollow">Wikipedia</a> for initial pointers.</p> http://mathoverflow.net/questions/64977/bipartite-travelling-salesman-problem/64990#64990 Answer by Per Alexandersson for "Bipartite" Travelling Salesman Problem? Per Alexandersson 2011-05-14T14:56:57Z 2011-05-14T14:56:57Z <p>You are looking for the max-flow-min-cut theorem: <a href="http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem</a></p>