The Hamiltonian (s,t)-path problem in odd-sized H-alphabet grid graphs

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.

کلیدواژه ها:

Hamiltonian path ، Hamiltonian cycle ، solid grid graphs ، alphabet grid graphs ، linear-time algorithm