A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole

DOI10.1016/j.tcs.2017.05.031zbMath1371.05287OpenAlexW2623199383MaRDI QIDQ2399614

Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date: 24 August 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.05.031

zbMATH Keywords

NP-completenessHamiltonian cycleHamiltonian pathgrid graphrectangular grid graphs with a rectangular hole

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (7)

Off-line exploration of rectangular cellular environments with a rectangular obstacle ⋮ A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole ⋮ The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs ⋮ A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes ⋮ On-line exploration of rectangular cellular environments with a rectangular hole ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian paths in some classes of grid graphs
• Approximating the longest paths in grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Hamiltonian properties of triangular grid graphs
• On Hamiltonian cycles and Hamiltonian paths
• Advances on the Hamiltonian problem -- a survey
• An efficient algorithm for constructing Hamiltonian paths in meshes
• The Hamiltonian circuit problem for circle graphs is NP-complete
• A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole
• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• Enumeration of Tours in Hamiltonian Rectangular Lattice Graphs
• Hamiltonian Properties of Grid Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Hamilton circuit problem on grids
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Hamilton Paths in Grid Graphs
• Computing and Combinatorics
• Hamiltonian paths in \(L\)-shaped grid graphs

This page was built for publication: A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole