Hamiltonian paths in some classes of grid graphs

DOI10.1155/2012/475087MaRDI QIDQ442933zbMATH OpenOpenAlexWikidataFDO

Authors Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date 6 August 2012

Published in Journal of Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

linear-time algorithms\(C\)-alphabet,\(E\)-alphabet\(F\)-alphabet\(L\)-alphabet

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Abstract: In this paper, we give the necessary and sufficient conditions for the existence of Hamiltonian paths in $L-$alphabet and $C-$alphabet grid graphs. We also present a linear-time algorithm for finding Hamiltonian paths in these graphs.

Recommendations

• Hamiltonian paths in \(L\)-shaped grid graphs
• Hamiltonian Properties of Grid Graphs
• scientific article; zbMATH DE number 4031743
• scientific article; zbMATH DE number 4091550
• Hamiltonian paths and hamiltonian connectivity in graphs
• Hamiltonian Paths and Cycles in Planar Graphs
• Hamilton paths in graphs whose vertices are graphs
• Hamiltonian paths in Cayley graphs
• Hamiltonian paths in distance graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• A theorem of Littlewood, Orlicz, and Grothendieck about sums in \(L^1(0,1)\)
• Advances on the Hamiltonian problem -- a survey
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Expected Computation Time for Hamiltonian Path problem
• Hamilton Paths in Grid Graphs
• Hamiltonian Properties of Grid Graphs
• Hamiltonian paths in some classes of grid graphs
• Hamiltonian properties of triangular grid graphs
• On Hamiltonian cycles and Hamiltonian paths
• Paths in interval graphs and circular arc graphs
• Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs
• The domination numbers of cylindrical grid graphs

Cited in

(27)

• Hamiltonian paths in \(L\)-shaped grid graphs
• scientific article; zbMATH DE number 2109328 (Why is no real title available?)
• scientific article; zbMATH DE number 6513170 (Why is no real title available?)
• Longest (s, t)-paths in L-shaped grid graphs
• The Hamiltonian properties of supergrid graphs
• 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
• Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs
• scientific article; zbMATH DE number 3884208 (Why is no real title available?)
• Hamiltonian (s, t)-paths in solid supergrid graphs
• Spanning closed trail and hamiltonian cycle in grid graphs
• 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
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• Cardinality constrained path covering problems in grid graphs
• scientific article; zbMATH DE number 4031743 (Why is no real title available?)
• Hamiltonian properties of triangular grid graphs
• scientific article; zbMATH DE number 2105044 (Why is no real title available?)
• Hamiltonian paths in some classes of grid graphs
• 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
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Bend complexity and Hamiltonian cycles in grid graphs
• Some new characterizations of Hamiltonian cycles in triangular grid graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• 2-Trees: Structural insights and the study of Hamiltonian paths
• The Hamiltonian connectivity of rectangular supergrid graphs
• The Hamilton circuit problem on grids

This page was built for publication: Hamiltonian paths in some classes of grid graphs

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