Complexity of the Mixed Postman Problem with Restrictions on the Arcs
作者： Zaragoza Martinez , Francisco Javier
DOI: 10.1109/ICEEE.2006.251877
关键词: Combinatorics 、 Graph 、 Time complexity 、 Graph theory 、 Mathematics 、 NP-complete 、 Polyhedron 、 Discrete mathematics 、 Integer programming 、 Mixed graph
摘要: The mixed postman problem consists of finding a minimum cost tour graph traversing all its vertices, edges, and arcs at least once. We consider the variant where must be traversed exactly prove that decision version this is NP-complete. give an integer programming formulation we one linear relaxations defines integral polyhedron can solved in polynomial time.
sci-hub.se 参考文章(8)
Balaji Raghavachari, Jeyakesavan Veerasamy, Approximation algorithms for postman problems The University of Texas at Dallas. ,(1999)
Zaragoza Martinez, Francisco Javier, Postman Problems on Mixed Graphs University of Waterloo. ,(2003)
Lester Randolph Ford, Flows in networks ,(1962)
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization Combinatorica. ,vol. 1, pp. 169- 197 ,(1981) , 10.1007/BF02579273
Edward Minieka, The Chinese Postman Problem for Mixed Networks Management Science. ,vol. 25, pp. 643- 648 ,(1979) , 10.1287/MNSC.25.7.643
Manfred W. Padberg, M. R. Rao, Odd Minimum Cut-Sets and b-Matchings Mathematics of Operations Research. ,vol. 7, pp. 67- 80 ,(1982) , 10.1287/MOOR.7.1.67
Thomas J. Schaefer, The complexity of satisfiability problems symposium on the theory of computing. pp. 216- 226 ,(1978) , 10.1145/800133.804350
William H. Cunningham, William J. Cook, Alexander Schrijver, William R. Pulleyblank, Combinatorial Optimization ,(1997)