Hello, I know how chinese postman algorithm works. But my confusion is on complexity. Is it possible to solve this on polynomial time?? because, if there are n odd vertices , then they can be paired (n-1)*(n-3)*(n-5)*.....1 So , to generate all possible pairing we need massive time if n is big.
So, My first question is , Is it possible to calculate pairing with any algorithm in polynomial time??
And, Is there another approach where pairing is not needed and can be solved on polynomial time??
Please answer.
I don't remember clearly Chinese Postman problem, but as far as I remember we needed there a polynomial algorithm that returns cheapest matching on 2n vertices (something like Hungarian and blossom at the same time). I don't know how it works or where you can find it, but such algorithm exists.
As a redcoder you should not forget this. If this type of problem is given in any codeforces contest you may loose rating.
I don't remember exact statement, but I know that once I will be presented it I would know how I can solve it using these matchings ;p