Exploiting planarity in separation routines for the symmetric traveling salesman problem

Applegate, 1998, On the solution of traveling salesman problems, Doc. Math. Extra Volume, ICM III, 645 S. Arora, M. Grigni, D. Karger, P. Klein, A. Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, in: Proceedings of the Ninth Annual ACM–SIAM Symposium on Discrete Algorithms, 1998, pp. 33–41 Barahona, 1986, On the cut polytope, Math. Program., 36, 157, 10.1007/BF02592023 Boyd, 2007, On the domino-parity inequalities for the STSP, Math. Program., 110, 501, 10.1007/s10107-006-0011-6 Carr, 1997, Separating clique tree and bipartition inequalities having a fixed number of handles and teeth in polynomial time, Math. Oper. Res., 22, 257, 10.1287/moor.22.2.257 Carr, 1996, Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time, vol. 1084, 460 Carr, 2004, Separation algorithms for classes of STSP inequalities arising from a new STSP relaxation, Math. Oper. Res., 29, 80, 10.1287/moor.1030.0058 Chalermsook, 2004, A deterministic near-linear time algorithm for finding minimum cuts in planar graphs Chvátal, 1973, Edmonds polytopes and weakly Hamiltonian graphs, Math. Program., 5, 29, 10.1007/BF01580109 Cook, 2005, A study of domino-parity and k-parity constraints for the TSP, vol. 3509, 452 Dantzig, 1954, Solution of a large-scale traveling salesman problem, Oper. Res., 2, 393 Deineko, 2006, Exact algorithms for the hamiltonian cycle problem in planar graphs, Oper. Res. Lett., 34, 269, 10.1016/j.orl.2005.04.013 Dijkstra, 1959, A note on two problems in connection with graphs, Numer. Math., 1, 269, 10.1007/BF01386390 Dorn, 2005, Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions, vol. 3669, 95 Edmonds, 1965, Maximum matching and a polyhedron with 0-1 vertices, J. Res. Nat. Bur. Standards, 69B, 125, 10.6028/jres.069B.013 Fleischer, 2006, Polynomial-time separation of a superclass of simple comb inequalities, Math. Oper. Res., 31, 696, 10.1287/moor.1060.0214 Fleischer, 1999, Separating maximally violated comb inequalites in planar graphs, Math. Oper. Res., 24, 130, 10.1287/moor.24.1.130 Goldberg, 1988, A new approach to the maximum flow problem, J. ACM, 35, 921, 10.1145/48014.61051 Grötschel, 1987, A cutting plane algorithm for minimum perfect 2-matching, Computing, 39, 327, 10.1007/BF02239975 Grötschel, 1988 Grötschel, 1979, On the symmetric travelling salesman problem I: Inequalities, Math. Program., 16, 265, 10.1007/BF01582116 Grötschel, 1979, On the symmetric travelling salesman problem II: Lifting theorems and facets, Math. Program., 16, 281, 10.1007/BF01582117 Held, 1962, A dynamic programming approach to sequencing problems, SIAM Rev., 10, 196 Henzinger, 1997, Faster shortest-path algorithms for planar graphs, J. Comput. System Sci., 55, 3, 10.1006/jcss.1997.1493 Jünger, 1995, The traveling salesman problem, vol. 7, 225 Jünger, 1997, The traveling salesman problem Letchford, 2000, Separating a superclass of comb inequalities in planar graphs, Math. Oper. Res., 25, 443, 10.1287/moor.25.3.443.12213 Letchford, 2002, Polynomial-time separation of simple comb inequalities, vol. 2337 Letchford, 2005, A fast algorithm for minimum weight odd cuts and circuits in planar graphs, Oper. Res. Lett., 33, 625, 10.1016/j.orl.2004.12.001 Letchford, 2004, A faster exact separation algorithm for blossom inequalities, vol. 3064 Lipton, 1979, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177, 10.1137/0136016 Naddef, 2002, Polyhedral theory and branch-and-cut algorithms for the symmetric TSP Naddef, 2004, The domino inequalities for the symmetric traveling salesman problem Naddef, 2003, The domino inequalities: New facets for the symmetric traveling salesman polytope, Math. Program., 98, 223, 10.1007/s10107-003-0403-9 Nagamochi, 1994, Implementing an efficient minimum capacity cut algorithm, Math. Program., 67, 325, 10.1007/BF01582226 Padberg, 1982, Odd minimum cut-sets and b-matchings, Math. Oper. Res., 7, 67, 10.1287/moor.7.1.67 Padberg, 1991, A branch-and-cut algorithm for the resolution of large-scale symmetric travelling salesman problems, SIAM Rev., 33, 60, 10.1137/1033004 Papadimitriou, 1993, The traveling salesman problem with distances one and two, Math. Oper. Res., 18, 1, 10.1287/moor.18.1.1 Shih, 1990, Unifying maximum cut and minimum cut of a planar graph, IEEE Trans. Comput., 39, 694, 10.1109/12.53581 Williams, 1964, Algorithm 232: Heapsort, ACM Commun., 7, 347, 10.1145/512274.512284