The Hamiltonian $(s,t)$-path problem in odd-sized $H$-alphabet grid graphs
نویسندگان
1 Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathum Thani 12120, Thailand
2 Thammasat Secondary School, Faculty of Learning Sciences and Education, Thammasat University, Pathum Thani 12120, Thailand
doi
10.22108/toc.2025.145023.2272چکیده
The Hamiltonian path problem is a well-known problem in graph theory with numerous applications in many fields such as routing, robotics, and parallel processing. In general, this problem is NP-complete for general grid graphs; however, efficient solutions can be found for specific classes of graphs. This paper investigates the Hamiltonian $(s,t)$-path problem in odd-sized $H$-alphabet grid graphs, a sub-class of solid grid graphs. We begin by establishing the conditions under which a Hamiltonian path between two given vertices s and t does not exist. For the cases where a Hamiltonian path exists, we propose an efficient linear-time algorithm to find a Hamiltonian path between the two given vertices.
