G. Cornuéjols
Abstract
This paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear equalities and inequalities. The central notion is that of a 3-edge cutset, namely, a set of 3 edges that, when removed, disconnects the graph. Conversely, our approach can be used to construct classes of graphs for which there exists a polynomial algorithm for the traveling salesman problem. The approach is illustrated on two examples, Halin graphs and prismatic graphs.
- 1 BACHEM, A., AND GROTSCHEL, M.maticsmOptimization and Operations Research, B. Korte, Ed. North Holland, Amsterdam, 1982, pp. 51-106.Google Scholar
- 2 BOULALA, M., AND UHRY, J. P.Polytope des ind6pendants d'un graphe s6rie-parall61e. Discrete Math. 27 (1979), 225-243.Google Scholar
- 3 CORNU~OLS, G., NADDEF, D., AND PULLEYBLANK, W. Halin graphs and the travelling salesman problem. Math. Prog. 16 (1983), 287-294.Google Scholar
- 4 CORNUEJOLS, G., AND PULLEYBLANK, W. The travelling salesman polytope and {0, 2}-matchings. Ann. Discrete Math. 16 (1982), 27-55.Google Scholar
- 5 CROWDER, H., AND PADBERG, M. W. Solving large-scale symmetric travelling salesman problems to optimality. Manage. Sci. 26 (1980), 495-509.Google Scholar
- 6 CUTLER, Efficient special case algorithm for the N line planar travelling salesman problem. Networks 10 (1980), 183-195.Google Scholar
- 7 EDMONDS, J. Maximum matching and a polyhedron with 0, 1 vertices. J. Res. Nat. Bur. Standards 69B (1965), 125-130.Google Scholar
- 8 EDMONDS, J.Matroid intersection. Ann. Disc. Math. 4 (1979), 39-49.Google Scholar
- 9 GARFINKEL, R. S.Minimizing wallpaper waste. Part I: A class of travelling salesman problems. Oper. Res. 25 (1977), 741-751.Google Scholar
- 10 GILES, F. R., AND TROTTER, L. E.On stable set polyhedra for Kt,3-free graphs. J. Comb. Theory Series B 31 (1981), 313-326.Google Scholar
- 11 GILMORE, P. C., AND GOMORY, R. E.Sequencing a one state-variable machine: A solvable case of the travelling salesman problem. Oper. Res. 12 (1964), 655-679.Google Scholar
- 12 GROTSCHEL, M.On the monotone symmetric travelling salesman problem: Hypohamiltonian/ hypotraceable graphs and facets. Math. Oper. Res. 5 (1980), 285-292.Google Scholar
- 13 GROTSCHEL, M. Polyedrische Characterisierungen kombinatorischen Optimierungsprobleme. Verlag Anton Hain, Meisenheim am Glan, Germany, 1977.Google Scholar
- 14 GROTSCHEL, M., Lov~,sz, L., AND SCHRIJVER, A.The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 ( 198 l), 169-197.Google Scholar
- 15 GROTSCHEL, M., AND PADBERG, M. W. On the symmetric travelling salesman problem I and II. Math. Prog. 16 (1979), 265-302.Google Scholar
- 16 GROTSCHEL, M., AND PADBERG, M. W. Polyhedral aspects of the traveling salesman problem i: Theory. To be published in The Traveling Salesman Problem, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Eds. Wiley, New York.Google Scholar
- 17 GROTSCHEL, M., AND PADBERG, M. W. Polyhedral aspects of the traveling salesman problem II: Computation. To be published in The Traveling Salesman Problem, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Eds. Wiley, New York.Google Scholar
- 18 GROTSCHEL, M., AND PULLEYBLANK, W.Clique tree inequalities and the symmetric travelling salesman problem. Report 81196-OR, Institut fiir Okonometrie und Operations Research, Bonn, Germany, 1981 (Math. Oper. Res., to be published). Google Scholar
- 19 HALIN, R.Studies on minimally n-connected graphs. Combinatorial Mathematics and Its Applications, D. J. A. Welsh, Ed. Academic Press, New York, 1971, pp. 129-136.Google Scholar
- 20 HELD, M., AND KARP, R.The travelling salesman problem and minimum spanning trees, Part I. Oper. Res. 18 (1970), 1138-1162.Google Scholar
- 21 HELD, M., AND KARP, R.The travelling salesman problem and minimum spanning trees, Part II. Math. Prog. 1 (1971), 6-25.Google Scholar
- 22 LAWLER, E. A solvable case of the travelling salesman problems. Math. Prog. i (1971), 267-269.Google Scholar
- 23 LITTLE, G., MURTY, K., SWEYNEY, D., AND KAREL, C.An algorithm for the travelling salesman problem. Oper. Res. 11 (1963), 972-989.Google Scholar
- 24 LovAsz, L., AND PLUMMER, M.On a family of planar bicritical graphs. Proc. London Math. Soc. 30(1975), 160-176.Google Scholar
- 25 MINTY, G.On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Series B 28 (1980), 284-304.Google Scholar
- 26 NADDEF, D., AND PULLEYBLANK, W.Ear decomposition of elementary graphs and GF2-rank of perfect matchings. Ann. Discrete Math. 16 (1982), 241-260.Google Scholar
- 27 PULLEYBLANK, W.The matching rank of Halin graphs. Rapport de Recherche 210 IMAG, Universit6 Scientifique et M6dicale de Grenoble, Grenoble, France, 1980.Google Scholar
- 28 RATLIFF, H. D., AND ROSENTHAL, A. S.Order-picking in a rectangular warehouse. A solvable case of the travelling salesman problem. Op. Res. 31 (1983), 507-521.Google Scholar
- 29 SBIHI, N.Algorithme de recherche d'un stable de cardinalit~ maximum dans un graphe sans 6toile. Discrete Math. 29 (1980), 53-76.Google Scholar
- 30 SYSLO, M. A new solvable case of the travelling salesman problem. Math. Prog. 4 (1973), 347- 348.Google Scholar
- 31 SYSLO, M., AND PROSKUROWSKI, A. On Halin graphs. In Graph Theory Lag6w 1981. Lecture Notes in Mathematics, vol. 1018. Springer-Vedag, Berlin-Heidelberg, 1981, pp. 248-256.Google Scholar
Index Terms
- The traveling salesman problem in graphs with 3-edge cutsets
Recommendations
Halin graphs and the travelling salesman problem
A Halin graphH=TźC is obtained by embedding a treeT having no nodes of degree 2 in the plane, and then adding a cycleC to join the leaves ofT in such a way that the resulting graph is planar. These graphs are edge minimal 3-connected, hamiltonian, and ...
On 3-Edge-Connected Supereulerian Graphs
The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger ...
Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is @W(n^0^.^6^9^4), and the circumference of a 3-connected claw-free graph ...
Comments