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

DOI10.1016/0377-2217(83)90161-3zbMath0496.90079OpenAlexW2032527321MaRDI 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 resultsimplementationelimination of variables1-tree relaxationsymmetric traveling salesman problemedge exchangesminimal 1-trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical optimization and variational techniques (65K10) Linear programming (90C05)

Related Items (25)

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

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

This page was built for publication: The symmetric traveling salesman problem and edge exchanges in minimal 1- trees