Exploiting planarity in separation routines for the symmetric traveling salesman problem

DOI10.1016/j.disopt.2007.05.002zbMath1151.90039OpenAlexW2135168424WikidataQ57702249 ScholiaQ57702249MaRDI QIDQ951094

Adam N. Letchford, Nicholas A. Pearson

Publication date: 29 October 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/44643/1/10.pdf

zbMATH Keywords

planar graphscutting planes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (1)

Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs

Uses Software

• heapsort

Cites Work

• A note on two problems in connexion with graphs
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs
• On the domino-parity inequalities for the STSP
• On the solution of traveling salesman problems
• Geometric algorithms and combinatorial optimization
• The domino inequalities: facets for the symmetric traveling salesman polytope
• Implementing an efficient minimum capacity cut algorithm
• A cutting plane algorithm for minimum perfect 2-matchings
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Separating Maximally Violated Comb Inequalities in Planar Graphs
• Separating a Superclass of Comb Inequalities in Planar Graphs
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• A Dynamic Programming Approach to Sequencing Problems
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A Study of Domino-Parity and k-Parity Constraints for the TSP
• A new approach to the maximum-flow problem
• A Separator Theorem for Planar Graphs
• Odd Minimum Cut-Sets and b-Matchings
• Separating Clique Trees and Bipartition Inequalities Having a Fixed Number of Handles and Teeth in Polynomial Time
• Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
• The Traveling Salesman Problem with Distances One and Two
• On the cut polytope
• Unifying maximum cut and minimum cut of a planar graph
• Solution of a Large-Scale Traveling-Salesman Problem
• Polynomial-Time Separation of a Superclass of Simple Comb Inequalities
• Algorithms – ESA 2005
• Maximum matching and a polyhedron with 0,1-vertices
• Edmonds polytopes and weakly hamiltonian graphs
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• Integer Programming and Combinatorial Optimization
• Faster shortest-path algorithms for planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Exploiting planarity in separation routines for the symmetric traveling salesman problem