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

DOI10.1016/J.DISOPT.2019.100554zbMATH Open1506.05113OpenAlexW2971529185MaRDI QIDQ2299983FDOQ2299983

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

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

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)

Cites Work

• On computing a longest path in a tree
• On computing longest paths in small graph classes
• Finding a Path of Superlogarithmic Length
• Finding a Longest Path in a Complete Multipartite Digraph
• Hamilton Paths in Grid Graphs
• On approximating the longest path in a graph
• Approximating the longest paths in grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian paths in some classes of grid graphs
• The Hamiltonian properties of supergrid graphs
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• On Hamiltonian cycles and Hamiltonian paths
• Hamiltonian paths in \(L\)-shaped grid graphs
• Computing and Combinatorics
• Algorithms for long paths in graphs
• The longest path problem is polynomial on cocomparability graphs
• The Hamiltonian connectivity of rectangular supergrid 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
• Title not available (Why is that?)
• Longest (s, t)-paths in L-shaped grid graphs

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
• On-line exploration of rectangular cellular environments with a rectangular hole
• Title not available (Why is that?)
• 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)