Optimal arcs for the traveling salesman problem

DOI10.1016/0893-9659(92)90028-8MaRDI QIDQ1195644zbMATH OpenOpenAlexFDO

Authors Richard H. Warren

Publication date 6 January 1993

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0893-9659(92)90028-8

zbMATH Keywords

NP-completetraveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Review text

This paper contains theoretical results and robust conclusions about the matrix structure of the traveling salesman problem. The results expand previous research advances of the author [ibid. 2, No. 3, 277-279 (1989; Zbl 0704.90075); and Linear Algebra Appl. 139, 53-62 (1990; Zbl 0727.90063) for classifying distance matrices; ibid. 160, 247-253 (1992; Zbl 0743.90078) for the 0,1 traveling salesman problem]. The classes of distance matrices which are analyzed are those for which an arc on an optimal tour can be identified in polynomial time. The 0,1 case is given special attention because it is NP-complete.

Recommendations

• scientific article; zbMATH DE number 34438
• scientific article; zbMATH DE number 795217
• A note on the traveling salesman problem
• The traveling salesman problem. I: Theoretical issues
• scientific article; zbMATH DE number 4027206

Cites work

• A polynomial-time solution to Papadimitriou and Steiglitz's ``traps
• Classes of matrices for the traveling salesman problem
• Classifying traveling salesman problems
• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 4039668 (Why is no real title available?)
• scientific article; zbMATH DE number 34438 (Why is no real title available?)
• Revisiting the 0,1 assignment problem
• Some Examples of Difficult Traveling Salesman Problems
• Special cases of travelling salesman problems and heuristics
• Tours for the traveling salesman

Cited in

(5)

• Tours for the traveling salesman
• Special cases of the traveling salesman problem
• scientific article; zbMATH DE number 4031431 (Why is no real title available?)
• The traveling salesman problem: the spectral radius and the length of an optimal tour
• Classes of matrices for the traveling salesman problem

This page was built for publication: Optimal arcs for the traveling salesman problem

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