[Boost-users] Minimum perfect matching

Subject: [Boost-users] Minimum perfect matching
From: Paolo Bolzoni (paolo.bolzoni.brown_at_[hidden])
Date: 2014-02-12 09:06:46

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