A new algorithm for the directed Chinese postman problem (Q1115814)

The directed Chinese Postman Problem can be transformed into a minimum cost flow problem over a derived network, or be transformed into a transportation problem in which the coefficients are determined by a shortest path problem over an extended network. Based on the Complementary Slackness Theorem, this paper will present an algorithm for the directed Chinese Postman Problem, which can be applied directly to the original network and, compared with the existing algorithms, has a better computational complexity \(O(kn^ 2)\) where k depends on the structure of the network. The algorithm is extended to the directed m-CPP case.