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

DOI10.1080/10556788.2022.2157001MaRDI QIDQ6175567zbMATH OpenFDO

Authors Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date 24 July 2023

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10556788.2022.2157001

zbMATH Keywords

grid graphHamiltonian cyclelinear-time algorithmoff-line explorationrectangular grid graphrectangular hole

Mathematics Subject Classification ID

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

Recommendations

• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time
• scientific article; zbMATH DE number 4031743
• The Hamilton circuit problem on grids
• Hamiltonian paths in some classes of grid graphs

Cites work

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

Cited in

(1)

• Hamiltonicity of rectangular grid graphs (meshes) with an L-shaped hole

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6175567)