Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time

DOI10.1016/J.AMC.2022.127513MaRDI QIDQ2673969zbMATH OpenOpenAlexWikidataFDO

Authors Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date 21 September 2022

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2022.127513

zbMATH Keywords

Hamiltonian cycle problemlinear-time algorithmsolid grid graphtruncated rectangular grid graphs

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• The Hamilton circuit problem on grids
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• scientific article; zbMATH DE number 4031743
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

Cites work

• An efficient algorithm for constructing Hamiltonian paths in meshes
• Computing and Combinatorics
• Graph theory with applications
• Hamilton Paths in Grid Graphs
• Hamiltonian cycles in \(k\)-partite graphs
• Hamiltonian paths in L-shaped grid graphs
• Hamiltonian Properties of Grid Graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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
• Regular non-Hamiltonian polyhedral graphs
• Survey on path and cycle embedding in some networks
• The Hamilton circuit problem on grids

Cited in

(12)

• Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• An approximation algorithm for the longest cycle problem in solid grid graphs
• scientific article; zbMATH DE number 4031743 (Why is no real title available?)
• 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
• A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes
• Spanning closed trail and hamiltonian cycle in grid graphs
• The Hamiltonian path graph is connected for simple s,t paths in rectangular grid graphs
• The Hamiltonian (s, t)-path problem in odd-sized H-alphabet grid graphs
• Hamiltonicity of rectangular grid graphs (meshes) with an L-shaped hole
• Modeling energy collection with shortest paths in rectangular grids: an efficient algorithm for energy harvesting
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

This page was built for publication: Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time

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