On the complexity of edge traversing

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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: DINIC, E A Algorithm for solution of a problem of maximum flow in a network with power estimation Soviet Math Dokl. 11, 5 (1970), 1277-1280
• 3: EDMONDS, J The Chinese Postman Problem Oper Res 13, Suppl 1 (1965), B73-B77
• 4: EDMONDS, J , AND JOHNSON, E L Matching, Euler tours and the Chinese Postman Math Programmtng 5, 1 (1973), 88-124
• 5: EULER, L Solutlo problematls ad geometrlam situs pertmentls Commentartt Academtae Petropohtanae 8 (1736), 128-140
• 6: FORD JR , L R, AND FULKERSON, D R Flows ~n Networks Princeton U Press, Princeton, N J., 1962
• 7: HARAaY, F Graph Theory Addison-Wesley, Reading, Mass, 1970
• 8: John Hopcroft , Robert Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, v.16 n.6, p.372-378, June 1973 [doi>10.1145/362248.362272]
• 9: KARP, R M Reduclblhty among combinatorial problems In Complexity of Computer Computatmns, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103.
• 10: KUHN, H W The Hungarian method for the assignment problem Naval Res Logistics Quart 2 (1955), 83-97
• 11: Me{-Ko, K Graphic programming using odd or even points Chtnese Math 1, (1962), 237-277
• 12: PAPnmM~TRIOU, C H The Euclidean TSP is NP-comp}ete TR #191, Dep ofElec Eng, Princeton U, Princeton, N J , 1975
• 13: PAPADIMITRIOU, C H, AND STZIGLITZ, K On the complexity of local search for the Traveling Salesman Problem TR #189, Dep of Elec Eng, Princeton U , Princeton, N j , 1975
• 14: SAHNI, S , AND GONZALES, T P-complete problems and approximate solutions Proc 15th Annual Symp on Switching and Automata Theory, 1974, pp 28-32 (avmlable from IEEE, New York)
• 15: R. Endre Tarjan, Testing graph connectivity, Proceedings of the sixth annual ACM symposium on Theory of computing, p.185-193, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803897]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Algorithms, Measurement, Performance, Theory, Verification