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

DOI10.1016/J.DAM.2011.08.010zbMATH Open1237.05115OpenAlexW2047176418MaRDI QIDQ765359FDOQ765359

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

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

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)

Cites Work

• Title not available (Why is that?)
• On computing a longest path in a tree
• Finding large cycles in Hamiltonian graphs
• On computing longest paths in small graph classes
• The Longest Path Problem Is Polynomial on Interval Graphs
• 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
• Title not available (Why is that?)
• On approximating the longest path in a graph
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Finding paths and cycles of superpolylogarithmic length
• Algorithms for long paths in 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
• Algorithms and complexity for geodetic sets on partial grids
• Hamiltonian paths in \(L\)-shaped grid graphs
• 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
• Title not available (Why is that?)
• 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)