Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time

作者：

Highlights：

• In this paper, we consider the problem of finding a Hamiltonian cycle for truncated rectangular grid graphs.

• The necessary conditions for these graphs to be Hamiltonian are given and a linear-time algorithm to find a Hamiltonian cycle, if there exists, is presented.

• The Hamiltonian cycle problem for solid grid graphs has been solved already in time O(n4) but we solved it in less time complexity for truncated rectangular grid graphs.

摘要

•In this paper, we consider the problem of finding a Hamiltonian cycle for truncated rectangular grid graphs.•The necessary conditions for these graphs to be Hamiltonian are given and a linear-time algorithm to find a Hamiltonian cycle, if there exists, is presented.•The Hamiltonian cycle problem for solid grid graphs has been solved already in time O(n4) but we solved it in less time complexity for truncated rectangular grid graphs.

论文关键词：Hamiltonian cycle problem,Solid grid graph,Truncated rectangular grid graphs,Linear-time algorithm

论文评审过程：Received 22 February 2022, Revised 18 August 2022, Accepted 27 August 2022, Available online 8 September 2022, Version of Record 8 September 2022.

论文官网地址：https://doi.org/10.1016/j.amc.2022.127513