Identification of non-optimal arcs for the traveling salesman problem

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

Roy Jonker, Ton Volgenant

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 problem3-optimalityelimination of arcsnon-optimal arcs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05)

Related Items

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, Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, A note on dual solutions of the assignment problem in connection with the traveling salesman problem, A note on the approximation of the asymmetric traveling salesman problem., The symmetric traveling salesman problem and edge exchanges in minimal 1- trees, Heuristic methods and applications: A categorized survey, Special cases of the traveling salesman problem, A note on finding a shortest complete cycle in an undirected graph

Cites Work

• 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
• Unnamed Item