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

DOI10.1080/10556788.2022.2157001zbMath1525.05102MaRDI QIDQ6175567

Alireza Bagheri, Fatemeh Keshavarz-Kohjerdi

Publication date: 24 July 2023

Published in: Optimization Methods and Software (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian cyclegrid graphrectangular holelinear-time algorithmrectangular grid graphoff-line exploration

Mathematics Subject Classification ID

Automated systems (robots, etc.) in control theory (93C85) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Artificial intelligence for robotics (68T40) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Unnamed Item
• Hamiltonian cycles in linear-convex supergrid graphs
• The Hamiltonian properties of supergrid graphs
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Hamiltonian properties of triangular grid graphs
• On Hamiltonian cycles and Hamiltonian paths
• Hamiltonian cycles in T-graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• Reconfiguring Hamiltonian cycles in L-shaped grid graphs
• A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole
• Hamiltonian Properties of Grid Graphs
• Hamilton Paths in Grid Graphs
• Hamiltonian cycles in k‐partite graphs
• Computing and Combinatorics
• Hamiltonian paths in \(L\)-shaped grid graphs

This page was built for publication: A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes