Finding Hamiltonian Paths between Two Given Vertices in Even-sized T-shaped Grid Graphs

Document Type : Persian Original Article

Authors

1 Department of Mathematics & Computer Science, Shahed University, Tehran, Iran

2 Department of Mathematics & Computer Science, Shahed University, Tehran, Iran

Abstract

One of the most popular problems in graph theory is the Hamiltonian path or cycle problem. This problem is NP-complete for general graphs and even some classes of graphs, including general grid graphs. In this paper, we study the problem of finding a Hamiltonian path between two given vertices s and t in even-sized T-shaped grid graphs, which is special case of grid graphs. This problem has many applications including in sweeping robots and in parallel processing. In this paper, first we give necessary conditions for the existence of Hamiltonian paths and cycles, then we present a linear-time algorithm for solving these problem.

Keywords

References

[1] R. Garey, D.S. Johnson, “Computers and intractability: a guide to the theory of NP-completeness”, Freeman, San Francisco, CA, 1979.
[2] S. Rahman and M. Kaykobad, “On Hamiltonian cycles and Hamiltonian paths,” Information Processing Letters, vol. 94, no. 1, pp. 37-41, 2005.
[3] Umans and W. Lenhart, “Hamiltonian cycles in solid grid graphs,” in Proceedings 38th Annual Symposium on Foundations of Computer Science, IEEE, pp. 496-505, 1997.
[4] Luccio and C. Mugnia, “Hamiltonian paths on a rectangular chessboard,” in Proceedings of the 16th Annual Allerton Conference, pp. 161-173, 1978.
[5] Itai, C.H. Papadimitriou, and J.L. Szwarcfiter, “Hamiltonian paths in grid graphs,” SIAM Journal on Computing, vol. 11, no. 4, pp. 676-686, 1982.
[6] D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Computing, vol. 28, no. 9, pp. 1293-1305, 2002.
[7] N. M. Salman, Hajo Broersma, and Edy Tri Baskoro, “Spanning 2-Connected Subgraphs in Alphabet Graphs, Special Classes of Grid Graphs,” Journal of Automata, Languages and Combinatorics, vol. 8, no. 4, pp. 675-681, 2003.
[8] Keshavarz‎‏-Kohjerdi and A. Bagheri, “Hamiltonian paths in some classes of grid graphs,” Journal of Applied Mathematics, vol. 2012, 2012.
[9] ف. کشاورز کوهجردی و ع. ر. باقری‏،” مسیرهای همیلتونی در گراف‌های توری الفبایی "، پانزدهمین کنفرانس دانشجویی مهندسی برق ایران، ۱۳۹۱.
[10] W. Chang, O. Navrátil, and S. L. Peng, “The end-to-end longest path problem on a mesh with a missing vertex," Frontiers in Artificial Intelligence and Applications, pp. 59-66, 2015.
[11] Keshavarz-Kohjerdi and A. Bagheri, ``Hamiltonian paths in ‎L-shaped grid graphs,” Theoretical Computer Science, vol. 621, pp. 37-56, 2016. ‎
[12] Keshavarz-Kohjerdi and A. Bagheri, “A ‎linear-‎time algorithm for finding Hamiltonian ‎‎‏(s, t)-‎paths in even-sized rectangular grid graphs with a rectangular hole,” Theoretical Computer Science, vol. 690, pp. 26-58, 2017.‎
[13] Keshavarz-Kohjerdi and A. Bagheri, “A linear-time algorithm for finding Hamiltonian ‎‎ (s, t)-paths in odd-sized rectangular grid graphs with a rectangular hole,” The Journal of Supercomputing, vol. 73, no. 9, pp. 3821-3860, 2017. ‎‎‎
[14] Keshavarz-Kohjerdi and A. Bagheri, “Linear-time algorithms for finding Hamiltonian and longest ‎‎(s, t)-paths in ‎‎C-shaped grid graphs,” Discrete Optimization, vol. 35, article 100554, 2020.‎
[15] Hydara, S. Gannes, N. Traore, and W.E. Kevin Yanogo, “A study of end-to-end Longest Path Problem with two missing vertices", National Dong Hwa University CSIE Department, 2017.
[16] Keshavarz-Kohjerdi, Off-line exploration of rectangular cellular environments with rectangular obstacle, Optimization Methods and Software, https://doi.org/10.1080/10556788.2021.1977811, 2021.
Journal of Soft Computing and Information Technology
Volume 11, Issue 2 - Serial Number 36
Summer
September 2022
Pages 1-12

Files

Share

How to cite

Statistics