Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood

DOI10.1007/BF02253612zbMath0821.90122MaRDI QIDQ1805008

Rainer E. Burkard, Vladimir G. Deǐneko

Publication date: 4 May 1995

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

traveling salesmanassignmentcyclic permutationssubtour patchingMonge-matrixpatching graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Hermitian, skew-Hermitian, and related matrices (15B57) Eulerian and Hamiltonian graphs (05C45)

Related Items

Special cases of travelling salesman problems and heuristics ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ The exponential multi-insertion neighborhood for the vehicle routing problem with unit demands ⋮ Perspectives of Monge properties in optimization ⋮ A survey of very large-scale neighborhood search techniques ⋮ GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY ⋮ Subclasses of solvable problems from classes of combinatorial optimization problems ⋮ A new ILP-based refinement heuristic for vehicle routing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The optimum assignments and a new heuristic approach for the traveling salesman problem
• Geometric applications of a matrix-searching algorithm
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Sequence comparison with mixed convex and concave costs
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• A new heuristic for the traveling salesman problem
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem