Hamiltonian paths in \(L\)-shaped grid graphs

DOI10.1016/j.tcs.2016.01.024zbMath1335.05100arXiv1602.07407OpenAlexW2282903323MaRDI QIDQ5964021

Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date: 26 February 2016

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

Full work available at URL: https://arxiv.org/abs/1602.07407

zbMATH Keywords

NP-completenessHamiltonian path\(L\)-shaped grid graphgrid graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45)

Related Items (13)

Off-line exploration of rectangular cellular environments with a rectangular obstacle ⋮ 1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids ⋮ 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 ⋮ The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs ⋮ 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids ⋮ The Hamiltonian path graph is connected for simple \(s, t\) paths in rectangular grid graphs ⋮ A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ The simple grid polygon exploration problem ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs ⋮ Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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 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

This page was built for publication: Hamiltonian paths in \(L\)-shaped grid graphs