Identification of non-optimal arcs for the traveling salesman problem

DOI10.1016/0167-6377(82)90002-5zbMath0487.90089MaRDI QIDQ1165781

Ton Volgenant, Roy Jonker

Publication date: 1982

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(82)90002-5

zbMATH Keywords

traveling salesman problem; 3-optimality; elimination of arcs; non-optimal arcs

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

65K05: Numerical mathematical programming methods

Related Items

A note on dual solutions of the assignment problem in connection with the traveling salesman problem, A note on finding a shortest complete cycle in an undirected graph, Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, The symmetric traveling salesman problem and edge exchanges in minimal 1- trees, Special cases of the traveling salesman problem, A note on the approximation of the asymmetric traveling salesman problem., Heuristic methods and applications: A categorized survey, Improving Christofides' lower bound for the traveling salesman problem, Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem

Cites Work

• Unnamed Item
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit
• Computer Solutions of the Traveling Salesman Problem