A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes

被引:0
作者
Keshavarz-Kohjerdi, Fatemeh [1 ,3 ]
Bagheri, Alireza [2 ]
机构
[1] Shahed Univ, Dept Comp Sci, Tehran, Iran
[2] Amirkabir Univ Technol, Dept Comp Engn, Tehran Polytech, Tehran, Iran
[3] Shahed Univ, Persian Gulf Highway,Front Imam Khomeini Holy Shri, Tehra, Iran
关键词
Hamiltonian cycle; grid graph; rectangular grid graph; rectangular hole; linear-time algorithm; off-line exploration; PATHS; T)-PATHS; (S;
D O I
10.1080/10556788.2022.2157001
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The Hamiltonian cycle problem is one of the most important problems in graph theory that has many applications. This problem is NP-complete for general grid graphs. For solid grid graphs, there are polynomial-time algorithms. Existence of polynomial-time algorithms for grid graphs with few holes has been asked in the literature. In this paper, we give a linear-time algorithm for rectangular grid graphs with two rectangular holes. This extends the previous result for rectangular grid graphs with one rectangular hole. We first present the forbidden conditions in which there is no Hamiltonian cycle for any grid graphs, including rectangular grid graphs with rectangular holes. We then show that if these forbidden conditions do not hold, then there exists a Hamiltonian cycle. The proof is constructive, therefore, it gives an algorithm. An application of the problem is in off-line robot exploration.
引用
收藏
页码:591 / 625
页数:35
相关论文
共 23 条
  • [1] THE HAMILTON CIRCUIT PROBLEM ON GRIDS
    AFRATI, F
    [J]. RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1994, 28 (06): : 567 - 582
  • [2] Not being (super)thin or solid is hard: A study of grid Hamiltonicity
    Arkin, Esther M.
    Fekete, Sandor P.
    Islam, Kamrul
    Meijer, Henk
    Mitchell, Joseph S. B.
    Nunez-Rodriguez, Yurai
    Polishchuk, Valentin
    Rappaport, David
    Xiao, Henry
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2009, 42 (6-7): : 582 - 605
  • [3] Chen SD, 2002, PARALLEL COMPUT, V28, P1293, DOI 10.1016/S0167-8191(02)00135-7
  • [4] Hamiltonian cycles in k-partite graphs
    DeBiasio, Louis
    Krueger, Robert A.
    Pritikin, Dan
    Thompson, Eli
    [J]. JOURNAL OF GRAPH THEORY, 2020, 94 (01) : 92 - 112
  • [5] Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
  • [6] Hamiltonian properties of triangular grid graphs
    Gordon, Valery S.
    Orlovich, Yury L.
    Werner, Frank
    [J]. DISCRETE MATHEMATICS, 2008, 308 (24) : 6166 - 6188
  • [7] Hou K, 2018, P 30 CAN C COMP GEOM, P114
  • [8] Hamiltonian cycles in linear-convex supergrid graphs
    Hung, Ruo-Wei
    [J]. DISCRETE APPLIED MATHEMATICS, 2016, 211 : 99 - 112
  • [9] The Hamiltonian properties of supergrid graphs
    Hung, Ruo-Wei
    Yao, Chih-Chia
    Chan, Shang-Ju
    [J]. THEORETICAL COMPUTER SCIENCE, 2015, 602 : 132 - 148
  • [10] Icking C, 2005, LECT NOTES COMPUT SC, V3595, P524, DOI 10.1007/11533719_53