1982/11/01 by Alon Itai, Christos H. Papadimitriou, Jayme L. Szwarcfiter · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Combinatorics #Mathematics #Travelling salesman problem #Grid #Lattice graph #Hamiltonian path #Discrete mathematics #Longest path problem #Path (computing) #Euclidean geometry #Graph #Computer science #Line graph #Mathematical optimization #Shortest path problem #Voltage graph
paper · doi:10.1137/0211056
openalex publication_date 1982/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A grid graph is a node-induced finite subgraph of the infinite grid. It is rectangular if its set of nodes is the product of two intervals. Given a rectangular grid graph and two of its nodes, we give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes. In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete. This provides a new, relatively simple, proof of the result that the Euclidean traveling salesman problem is NP-complete.