On two geometric problems related to the travelling salesman problem

Christofides, 1976, Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Technical Report CMU

Garey, 1976, Some NP-complete geometric problems, 10

Garey, 1979

Johnson, 1982, Computational complexity and the travelling salesman problem

Johnson, 1982, Worst-case analysis of heuristics

Itai, 1982, Hamilton paths in grid graphs, Siam J. Comput., 10.1137/0211056

Karp, 1972, Reducibility among combinatorial problems, 85

Lawler, 1982

Papadimitriou, 1977, The Euclidean travelling salesman problem is NP-complete, Theor. Comput. Sci., 4, 237, 10.1016/0304-3975(77)90012-3

Plesnik, 1979, The NP-completeness of the Hamilton cycle problem for planar digraphs of degree bound two, Inform. Process. Lett., 8, 199, 10.1016/0020-0190(79)90023-1

Papadimitriou, 1976, Some complexity results for the travelling salesman problem, 1

Shamos, 1975

Shiloach, 1976, Linear and Planar Arrangements of Graphs