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

DOI10.1016/J.DAM.2011.08.010MaRDI QIDQ765359zbMATH OpenOpenAlexFDO

Authors 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 cycleHamiltonian pathlinear time algorithmgrid graphlongest path problemrectangular grid graph

Mathematics Subject Classification ID

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

Recommendations

• Longest (s, t)-paths in L-shaped grid graphs
• An approximation algorithm for the longest path problem in solid grid graphs
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• scientific article; zbMATH DE number 4031743
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Algorithms for long paths in graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Finding Long Paths, Cycles and Circuits
• Finding a Longest Path in a Complete Multipartite Digraph
• Finding a Path of Superlogarithmic Length
• Finding large cycles in Hamiltonian graphs
• Finding paths and cycles of superpolylogarithmic length
• Hamilton Paths in Grid Graphs
• On approximating the longest path in a graph
• On computing a longest path in a tree
• On computing longest paths in small graph classes
• The Longest Path Problem Is Polynomial on Interval Graphs

Cited in

(21)

• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Approximating the longest paths in grid graphs
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• The Hamiltonian connectivity of rectangular supergrid graphs
• Longest (s, t)-paths in L-shaped grid graphs
• Further study on ``An extended shortest path problem a data envelopment analysis approach
• Hamiltonian paths in L-shaped grid graphs
• Algorithms and complexity for geodetic sets on partial grids
• Efficient all path score computations on grid graphs
• A genetic algorithm for the picture maze generation problem
• QUBO formulations of the longest path problem
• A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian paths in some classes of grid graphs
• The Hamiltonian properties of supergrid graphs
• The longest path problem in odd-sized O-shaped grid graphs
• A polynomial time algorithm for longest paths in biconvex graphs
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)
• 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

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

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