The maximum travelling salesman problem on symmetric Demidenko matrices

DOI10.1016/S0166-218X(99)00148-1zbMath0945.90048OpenAlexW2098484303MaRDI QIDQ1962061

Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 20 March 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00148-1

zbMATH Keywords

computational complexitycombinatorial optimizationpolynomial algorithmtravelling salesman problemDemidenko conditionKalmanson conditionSupnick condition

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

An approximation algorithm for the maximum traveling salesman problem ⋮ A new asymmetric pyramidally solvable class of the traveling salesman problem ⋮ An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem ⋮ The maximum traveling salesman problem on van der Veen matrices ⋮ Algorithms – ESA 2004 ⋮ Four-point conditions for the TSP: the complete complexity classification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extreme Hamiltonian lines
• Hamiltonian properties of Toeplitz graphs
• Maximizing traveling salesman problem for special matrices
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
• Edgeconvex Circuits and the Traveling Salesman Problem
• Extreme Hamiltonian Circuits. Resolution of the Convex-Odd Case
• Extreme Hamiltonian Circuits. Resolution of the Convex-Even Case