Page 1 of 1
about chinese postman problem
Posted: Fri May 27, 2005 9:22 am
by Yu Fan
could someone give me an algorithm of the minimal cost matching in chinese postman problem?
i saw some webpage says that there is a O(n+3) algorithm but it didn't provide it...
Posted: Thu Jun 02, 2005 4:45 am
by gvcormac
I assume you mean Chinese Postman in an undirected graph. This reduces to min-cost general (non-bipartite) matching. There's a polytime algorithm, but it is incomprehensible to most humans and I'm not aware of any simple implementation. If somebody has a simple implementation, I would be delighted to see it.
If the graph is directed, it reduces to min-cost bipartite matching. Still a bit of code, but within the realm of possibility in a programming contest.
my approach..
Posted: Mon Jun 13, 2005 12:17 pm
by sohel
I usually (well, all the time) implement this part using backtracking and so far have managed to avoid TLE..
It works fine for 13/14 nodes, but for higher values i don't think backtracking will suffice.
How does everyone else implement this part.. backtracking or something else..
when i say 'this part' i mean minimal cost matching.
