A linear-time algorithm for finding Hamiltonian (s, t)-paths in even-sized rectangular grid graphs with a rectangular hole

作者：Keshavarz Kohjerdi Fatemeh^*; Bagheri Alireza

来源：Theoretical Computer Science, 2017, 690: 26-58.

DOI：10.1016/j.tcs.2017.05.031

• Grid graph
• Hamiltonian path
• Hamiltonian cycle
• Rectangular grid graphs with a rectangular
• hole
• NP-complete

The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give the necessary conditions for the existence of a Hamiltonian path between two given vertices in a rectangular grid graph with a rectangular hole; where the size of graph is even. In addition, we show that the Hamiltonian path in these graphs can be computed in linear-time.

• 出版日期2017-8-22