Optimal arcs for the traveling salesman problem (Q1195644)

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.