Exploiting planarity in separation routines for the symmetric traveling salesman problem
type: Item
instance of: scholarly article
title: Exploiting planarity in separation routines for the symmetric traveling salesman problem
zbMATH Open document ID: 1151.90039
author: Adam N. Letchford
author: Nicholas A. Pearson
published in: Discrete Optimization
publication date: 2008-10-29T00:00:00Z
full work available at URL: 10.pdf
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 5358784
zbMATH Keywords: planar graphs
zbMATH Keywords: cutting planes
describes a project that uses: heapsort
MaRDI profile type: Publication
OpenAlex ID: W2135168424
Wikidata QID: Q57702249
cites work: On the solution of traveling salesman problems
cites work: Q4250161
cites work: On the cut polytope
cites work: On the domino-parity inequalities for the STSP
cites work: Separating Clique Trees and Bipartition Inequalities Having a Fixed Number of Handles and Teeth in Polynomial Time
cites work: Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
cites work: Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
cites work: Q5501344
cites work: Edmonds polytopes and weakly hamiltonian graphs
cites work: A Study of Domino-Parity and k-Parity Constraints for the TSP
cites work: Solution of a Large-Scale Traveling-Salesman Problem
cites work: Exact algorithms for the Hamiltonian cycle problem in planar graphs
cites work: A note on two problems in connexion with graphs
cites work: Algorithms – ESA 2005
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Polynomial-Time Separation of a Superclass of Simple Comb Inequalities
cites work: Separating maximally violated comb inequalities in planar graphs
cites work: A new approach to the maximum-flow problem
cites work: A cutting plane algorithm for minimum perfect 2-matchings
cites work: Geometric algorithms and combinatorial optimization
cites work: On the symmetric travelling salesman problem I: Inequalities
cites work: On the symmetric travelling salesman problem II: Lifting theorems and facets
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: Faster shortest-path algorithms for planar graphs
cites work: Q4845366
cites work: Q4398370
cites work: Separating a superclass of comb inequalities in planar graphs
cites work: Q4737521
cites work: A fast algorithm for minimum weight odd circuits and cuts in planar graphs
cites work: Integer Programming and Combinatorial Optimization
cites work: A Separator Theorem for Planar Graphs
cites work: Q4461904
cites work: Q5465114
cites work: The domino inequalities: facets for the symmetric traveling salesman polytope
cites work: Implementing an efficient minimum capacity cut algorithm
cites work: Odd Minimum Cut-Sets and b-Matchings
cites work: A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
cites work: The Traveling Salesman Problem with Distances One and Two
cites work: Unifying maximum cut and minimum cut of a planar graph
DOI: 10.1016/J.DISOPT.2007.05.002
Recommended article: Efficient separation routines for the symmetric traveling salesman problem. I: General tools and comb separation
Recommended article: Efficient separation routines for the symmetric traveling salesman problem. II: Separating multi handle inequalities.
Recommended article: A new class of cutting planes for the symmetric travelling salesman problem
Recommended article: Q4263707
Recommended article: Symmetric travelling salesman problem. Some new algorithmic possibilities
Recommended article: The symmetric travelling salesman problem. II: New low bounds
Recommended article: The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
Recommended article: Solution of large-scale symmetric travelling salesman problems
Recommended article: On the graphical relaxation of the symmetric traveling salesman polytope
Recommended article: Symmetric traveling salesman problems
description: scientific article; zbMATH DE number 5358784