On the complexity of edge traversing

Christos H. Papadimitriou

Abstract

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.
BibTeX
@article{papadimitriou1976complexity,
  author = {Christos H. Papadimitriou},
  title = {{On the complexity of edge traversing}},
  journal = {J. ACM},
  year = {1976},
  doi = {10.1145/321958.321974},
}

Loading related content...

Figure