It is shown that the Chinese Postman Problem, although tractable in the totally directed and the totally undirected cases, is NP-complete in the mixed case. A simpler version of the same problem is shown algorithmically equivalent to the max-flow problem with unit edge capacities.
No takes yet. Share an insight, caveat, or question.
Christos H. Papadimitriou (1976) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: