The traveling salesman problem in graphs with 3-edge cutsets
作者： G. Cornuéjols , D. Naddef , W. Pulleyblank
DOI: 10.1145/3149.3154
关键词:
摘要: This paper analyzes decomposition properties of a graph that, when they occur, permit polynomial solution the traveling salesman problem and description polytope by system linear equalities inequalities. The central notion is that 3-edge cutset, namely, set 3 edges removed, disconnects graph. Conversely, our approach can be used to construct classes graphs for which there exists algorithm problem. illustrated on two examples, Halin prismatic graphs.
acm.org
sci-hub.se 参考文章(25)
Maciej M. Sysło, Andrzej Proskurowski, On Halin graphs Springer, Berlin, Heidelberg. pp. 248- 256 ,(1983) , 10.1007/BFB0071635
Achim Bachem, Martin Grötschel, New aspects of polyhedral theory ,(1982)
Martin Grötschel, Manfred W. Padberg, On the symmetric travelling salesman problem II: Lifting theorems and facets Mathematical Programming. ,vol. 16, pp. 281- 302 ,(1979) , 10.1007/BF01582117
Gérard Cornuéjols, William Pulleyblank, The Travelling Salesman Polytope and {0, 2}-Matchings North-holland Mathematics Studies. ,vol. 66, pp. 27- 55 ,(1982) , 10.1016/S0304-0208(08)72442-3
George J Minty, On maximal independent sets of vertices in claw-free graphs Journal of Combinatorial Theory, Series B. ,vol. 28, pp. 284- 304 ,(1980) , 10.1016/0095-8956(80)90074-X
Najiba Sbihi, Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile Discrete Mathematics. ,vol. 29, pp. 53- 76 ,(1980) , 10.1016/0012-365X(90)90287-R
Mouloud Boulala, Jean-Pierre Uhry, Polytope des independants d'un graphe serie-parallele Discrete Mathematics. ,vol. 27, pp. 225- 243 ,(1979) , 10.1016/0012-365X(79)90160-2
Michael Held, Richard M. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees Operations Research. ,vol. 18, pp. 1138- 1162 ,(1970) , 10.1287/OPRE.18.6.1138
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
H. Donald Ratliff, Arnon S. Rosenthal, Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem Operations Research. ,vol. 31, pp. 507- 521 ,(1983) , 10.1287/OPRE.31.3.507