A linear-time algorithm for the longest path problem in rectangular grid graphs

DOI10.1016/J.DAM.2011.08.010zbMath1237.05115OpenAlexW2047176418MaRDI QIDQ765359

Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri, Asghar Asgharian Sardroud

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.08.010

zbMATH Keywords

Hamiltonian cyclelinear time algorithmHamiltonian pathgrid graphlongest path problemrectangular grid graph

Mathematics Subject Classification ID

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

Related Items (17)

An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Hamiltonian cycles in linear-convex supergrid graphs ⋮ Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths ⋮ A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole ⋮ QUBO formulations of the longest path problem ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Hamiltonian paths in some classes of grid graphs ⋮ Unnamed Item ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ Unnamed Item ⋮ The Hamiltonian properties of supergrid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ The longest path problem in odd-sized \(O\)-shaped grid graphs ⋮ Hamiltonian paths in \(L\)-shaped grid graphs ⋮ A genetic algorithm for the picture maze generation problem ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs ⋮ An approximation algorithm for the longest path problem in solid grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Algorithms for long paths in graphs
• On computing a longest path in a tree
• An efficient algorithm for constructing Hamiltonian paths in meshes
• ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
• The Longest Path Problem Is Polynomial on Interval Graphs
• Finding paths and cycles of superpolylogarithmic length
• Finding Long Paths, Cycles and Circuits
• Finding a Path of Superlogarithmic Length
• Finding a Longest Path in a Complete Multipartite Digraph
• Hamilton Paths in Grid Graphs

This page was built for publication: A linear-time algorithm for the longest path problem in rectangular grid graphs