algorithm for Chinese postman circuit in a bidirected graph

Question

Im looking for an algorithm that finds a Chinese postman circuit in a bidirected graph. Bidirected graph here is not the symmetric directed graph, but the graph introduced by Edmonds & Johnson in 1970.

I found few papers that solved similar problem based on a paper published by Harold N Gabow in i983, but there was no formalized algorithm; they just mentioned that the problem can be reduced/related to perfect b-matching, bidirected network flow.. and so on, which i cannot understand so far.

if anyone knows the concept and algorithm for that, please give me some advises.

Answer 1

You can look at this paper to find a solution to the chinese postman problem.

Answer 2

Most algorithms for finding a chinese postman circuit transfers the problem to finding a Hamilton circuit. If this is not possible is the graph extended so that it is possible to find a hamilton circuit.

In a undirected graph is a hamilton circuit possible when all nodes has a even degree. If this is not the case must the nodes with odd degree be extended with one more edge. This results in a pairing problem.

I hope this will help with your bidirected graph problem. Maybe I can help you further if you precise your question