Linear-time algorithms for finding Hamiltonian and longest (s,t)-paths in C-shaped grid graphs

DOI10.1016/J.DISOPT.2019.100554MaRDI QIDQ2299983zbMATH OpenOpenAlexFDO

Authors Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date 24 February 2020

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2019.100554

zbMATH Keywords

grid graph\(C\)-shaped grid graphHamiltonian \((s,t)\)-pathHamiltonian cyclelongest \((s,t)\)-path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• Longest (s, t)-paths in L-shaped grid graphs
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• Hamiltonian paths in \(L\)-shaped grid graphs
• Hamiltonian paths in some classes of grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs

Cites work

• scientific article; zbMATH DE number 2105044 (Why is no real title available?)
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Algorithms for long paths in graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Approximating the longest paths in grid graphs
• Computing and Combinatorics
• Finding a Longest Path in a Complete Multipartite Digraph
• Finding a Path of Superlogarithmic Length
• Hamilton Paths in Grid Graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian paths in \(L\)-shaped grid graphs
• Hamiltonian paths in some classes of grid graphs
• Longest (s, t)-paths in L-shaped grid graphs
• On Hamiltonian cycles and Hamiltonian paths
• On approximating the longest path in a graph
• On computing a longest path in a tree
• On computing longest paths in small graph classes
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• The Hamiltonian connectivity of rectangular supergrid graphs
• The Hamiltonian properties of supergrid graphs
• The longest path problem is polynomial on cocomparability graphs
• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths

Cited in

(12)

• A linear-time algorithm for the longest path problem in rectangular grid graphs
• 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
• Longest (s, t)-paths in L-shaped grid graphs
• A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes
• Hamiltonian paths in \(L\)-shaped grid graphs
• scientific article; zbMATH DE number 1445365 (Why is no real title available?)
• On-line exploration of rectangular cellular environments with a rectangular hole
• The longest path problem in odd-sized \(O\)-shaped grid graphs
• Hamiltonian (s, t)-paths in solid supergrid graphs
• Off-line exploration of rectangular cellular environments with a rectangular obstacle
• An approximation algorithm for finding long paths in Hamiltonian graphs

This page was built for publication: Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs

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