On the traveling salesman problem with a relaxed Monge matrix

DOI10.1016/S0020-0190(98)00119-7zbMATH Open1339.90275OpenAlexW1996007173MaRDI QIDQ293365FDOQ293365

Authors Rainer E. Burkard, Vladimir G. Deineko 

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001197?np=y

zbMATH Keywords

algorithmstraveling salesman problemEuclidean TSPMonge matrixpyramidally solvable case

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• The travelling salesman problem on permuted Monge matrices
• On the recognition of permuted Supnick and incomplete Monge matrices
• One-Sided Monge TSP Is NP-Hard
• Pyramidal tours and the traveling salesman problem
• A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems

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?)
• A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
• Edgeconvex Circuits and the Traveling Salesman Problem
• Extrema in Space-Time
• Extreme Hamiltonian lines
• On the recognition of permuted Supnick and incomplete Monge matrices
• Perspectives of Monge properties in optimization
• Three easy special cases of the euclidean travelling salesman problem
• Universal conditions for algebraic travelling salesman problems to be efficiently solvable
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

Cited in

(7)

• OR Utopia
• The Lazy Travelling Salesman Problem in $\mathbb{R}^2$
• One-Sided Monge TSP Is NP-Hard
• Generalisations of the Gilmore-Gomory traveling salesman problem and the Gilmore-Gomory scheme: a survey
• The cone of Monge matrices: Extremal rays and applications
• The travelling salesman problem on permuted Monge matrices
• Relaxed tours and path ejections for the traveling salesman problem

This page was built for publication: On the traveling salesman problem with a relaxed Monge matrix

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