Good triangulations yield good tours

DOI10.1016/J.COR.2006.03.025MaRDI QIDQ2384914zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Adam N. Letchford, Nicholas A. Pearson

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

Delaunay triangulationtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• A delaunay triangulation‐based heuristic for the euclidean steiner problem
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Fast Algorithms for Geometric Traveling Salesman Problems
• scientific article; zbMATH DE number 1163704

Cites work

• A cutting plane procedure for the travelling salesman problem on road networks
• A Dynamic Programming Approach to Sequencing Problems
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Classes of graphs which approximate the complete Euclidean graph
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Fast Heuristics for Large Geometric Traveling Salesman Problems
• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 1079755 (Why is no real title available?)
• scientific article; zbMATH DE number 2064405 (Why is no real title available?)
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Separating a superclass of comb inequalities in planar graphs
• Separating maximally violated comb inequalities in planar graphs
• The greedy and Delaunay triangulations are not bad in the average case
• The greedy triangulation can be computed from the Delaunay triangulation in linear time
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The relative neighbourhood graph of a finite planar set
• The traveling salesman problem and its variations
• The traveling salesman problem on a graph and some related integer polyhedra
• The Traveling Salesman Problem with Distances One and Two
• The travelling salesman and the PQ-tree.
• There are planar graphs almost as good as the complete graph
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(7)

• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• New edges not used in shortest tours of TSP
• Novel concave hull-based heuristic algorithm for TSP
• Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
• Finding good tours for huge Euclidean TSP instances by iterative backbone contraction
• Computing compatible tours for the symmetric traveling salesman problem
• Edge sparsification for geometric tour problems

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Good triangulations yield good tours

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2384914)