On the complexity of edge traversing
Lists
Only you see this
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...