The symmetric traveling salesman problem and edge exchanges in minimal 1- trees

DOI10.1016/0377-2217(83)90161-3zbMath0496.90079MaRDI QIDQ1170119

Ton Volgenant, Roy Jonker

Publication date: 1983

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(83)90161-3

zbMATH Keywords

computational results; implementation; elimination of variables; 1-tree relaxation; symmetric traveling salesman problem; edge exchanges; minimal 1-trees

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C35: Extremal problems in graph theory

65K10: Numerical optimization and variational techniques

90C05: Linear programming

Related Items

A gene-pool based genetic algorithm for TSP, Improved algorithms for the Steiner problem in networks, The symmetric clustered traveling salesman problem, On dual solutions of the linear assignment problem, Transforming asymmetric into symmetric traveling salesman problems, Minimum deviation and balanced optimization: A unified approach, Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations, A note on finding a shortest complete cycle in an undirected graph, Edge exchanges in the degree-constrained minimum spanning tree problem, A Lagrangean approach to the degree-constrained minimum spanning tree problem, The symmetric traveling salesman problem and edge exchanges in minimal 1- trees, Optimizing tabu list size for the traveling salesman problem, An empirical study of a new metaheuristic for the traveling salesman problem, A branch and bound algorithm for symmetric 2-peripatetic salesman problems, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Solving some lexicographic multi-objective combinatorial problems, Fictitious upper bounds in an algorithm for the symmetric traveling salesman problem, New lower bounds for the symmetric travelling salesman problem, A note on relatives to the Held and Karp 1-tree problem, A tabu search algorithm for the Min-Max \(k\)-Chinese postman problem, Some inverse optimization problems under the Hamming distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• Identification of non-optimal arcs for the traveling salesman problem
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• A Dynamic Programming Approach to Sequencing Problems
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Computer Solutions of the Traveling Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution Problems