Hi Paolo, Yes, the Christofides algorithm requires a minimum weight perfect matching, and unfortunately there's no simple reduction from the problem of finding a weighted matching to the problem of finding a maximum cardinality matching. I haven't used metric_tsp_approx before, but if you're just adding one node n to an already complete graph and connecting it to s and d, could you just add all of the other edges between n and other nodes in the graph and set those edge weights to "infinity" (something bigger than the sum of all of the edge weights in the graph) to force metric_tsp_approx to avoid those edges? -Aaron On Wed, Feb 12, 2014 at 6:06 AM, Paolo Bolzoni < paolo.bolzoni.brown@gmail.com> wrote:
Dear list,
I am using boost graph and I need to solve a variant of the classic TSP. Boost providess a function (metric_tsp_approx) to get a Halmintonian cycle over a full connected metric weighted graph. However I need something slightly different.
I need a path that visits all vertices starting and ending to two well known vertices (let be s and d). Seeking around, I found the suggestion of adding a node connected to s d and with the weight of the edge (s,d). The TSP solution of the new graph is the solution, just removing the new node.
The problem is that now the graph is not complete anymore so the metric_tsp_approx's approach does not work anymore.
Another possiblity is using a variant of Christofides algorithm, but one of the passages of that is the minimum weight perfect matching.
I am a little confused by the documentation of the functions about Maximum Cardinality Matching(1), it is possible to use them to find the a maximum cardinality matching so that the total weight of all selected edges is minimal?
Otherwise, is there an alternate approach to my problem?
Yours faithfully, Paolo
(1) http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/maximum_matching.html _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users