Hamilton Paths in Grid Graphs | Zendy

Alon Itai | Zendy; Christos H. Papadimitriou | Zendy; Jayme L. Szwarcfiter | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Hamilton Paths in Grid Graphs

Author(s) -

Alon Itai,

Christos H. Papadimitriou,

Jayme L. Szwarcfiter

Publication year - 1982

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0211056

Subject(s) - 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 , geometry , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research