Good triangulations yield good tours
From MaRDI portal
Publication:2384914
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
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
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