The maximum travelling salesman problem on symmetric Demidenko matrices

DOI10.1016/S0166-218X(99)00148-1MaRDI QIDQ1962061zbMATH OpenOpenAlexFDO

Authors Vladimir G. Deineko, Gerhard J. Woeginger

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)

Recommendations

• A bound for the symmetric travelling salesman problem through matroid formulation
• Maximizing traveling salesman problem for special matrices
• The Travelling Salesman Problem in symmetric circulant matrices with two stripes
• scientific article; zbMATH DE number 1855663
• The travelling salesman problem on permuted Monge matrices
• THE MAXIMUM TRAVELING SALESMAN PROBLEM ON BANDED MATRICES
• scientific article; zbMATH DE number 1342125
• The symmetric quadratic traveling salesman problem
• Symmetric traveling salesman problems
• scientific article; zbMATH DE number 1187152

Cites work

• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 3571852 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
• Edgeconvex Circuits and the Traveling Salesman Problem
• Extreme Hamiltonian Circuits. Resolution of the Convex-Even Case
• Extreme Hamiltonian Circuits. Resolution of the Convex-Odd Case
• 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

Cited in

(15)

• Algorithms – ESA 2004
• THE MAXIMUM TRAVELING SALESMAN PROBLEM ON BANDED MATRICES
• scientific article; zbMATH DE number 1535433 (Why is no real title available?)
• Travelling salesman paths on Demidenko matrices
• A new asymmetric pyramidally solvable class of the traveling salesman problem
• An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
• Four-point conditions for the TSP: the complete complexity classification
• A bound for the symmetric travelling salesman problem through matroid formulation
• Maximum travelling salesman problem. I
• scientific article; zbMATH DE number 1187152 (Why is no real title available?)
• An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem
• The maximum traveling salesman problem on van der Veen matrices
• An approximation algorithm for the maximum traveling salesman problem
• The travelling salesman problem on permuted Monge matrices
• Maximizing traveling salesman problem for special matrices

This page was built for publication: The maximum travelling salesman problem on symmetric Demidenko matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962061)