On the complexity of edge traversing
- 1 July 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (3) , 544-554
- https://doi.org/10.1145/321958.321974
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.Keywords
This publication has 6 references indexed in Scilit:
- P-complete problems and approximate solutionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Testing graph connectivityPublished by Association for Computing Machinery (ACM) ,1974
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Flows in NetworksPublished by Walter de Gruyter GmbH ,1963
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955