Good triangulations yield good tours

DOI10.1016/j.cor.2006.03.025zbMath1141.90032OpenAlexW2112351359WikidataQ57702257 ScholiaQ57702257MaRDI QIDQ2384914

Nicholas A. Pearson, Adam N. Letchford

Publication date: 10 October 2007

Published in: Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

traveling salesman problemDelaunay triangulation

Mathematics Subject Classification ID

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

Related Items

Novel concave hull-based heuristic algorithm for TSP, Unnamed Item, Computing compatible tours for the symmetric traveling salesman problem, Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The greedy and Delaunay triangulations are not bad in the average case
• A cutting plane procedure for the travelling salesman problem on road networks
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• The relative neighbourhood graph of a finite planar set
• Classes of graphs which approximate the complete Euclidean graph
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• The traveling salesman problem and its variations
• There are planar graphs almost as good as the complete graph
• The greedy triangulation can be computed from the Delaunay triangulation in linear time
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• The Travelling Salesman and the PQ-Tree
• Separating Maximally Violated Comb Inequalities in Planar Graphs
• Separating a Superclass of Comb Inequalities in Planar Graphs
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Dynamic Programming Approach to Sequencing Problems
• The traveling salesman problem on a graph and some related integer polyhedra
• TSPLIB—A Traveling Salesman Problem Library
• Fast Heuristics for Large Geometric Traveling Salesman Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• The Traveling Salesman Problem with Distances One and Two