Longest (s, t)-paths in L-shaped grid graphs

DOI10.1080/10556788.2018.1460665zbMath1414.05164OpenAlexW2802907784MaRDI QIDQ5379463

Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date: 12 June 2019

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556788.2018.1460665

zbMATH Keywords

Hamiltonian pathlongest path\(L\)-shaped grid graphgrid graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• Hamiltonian paths in some classes of grid graphs
• The Hamiltonian properties of supergrid 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
• Algorithms for long paths in graphs
• Hamiltonian properties of triangular grid graphs
• On computing a longest path in a tree
• An efficient algorithm for constructing Hamiltonian paths in meshes
• The longest path problem is polynomial on cocomparability graphs
• A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole
• An approximation algorithm for the longest path problem in solid grid graphs
• ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
• The Longest Path Problem Is Polynomial on Interval Graphs
• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• Finding paths and cycles of superpolylogarithmic length
• Finding Long Paths, Cycles and Circuits
• Hamiltonian Properties of Grid Graphs
• Finding a Path of Superlogarithmic Length
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Finding a Longest Path in a Complete Multipartite Digraph
• Hamilton Paths in Grid Graphs
• Computing and Combinatorics
• Hamiltonian paths in \(L\)-shaped grid graphs

This page was built for publication: Longest (s, t)-paths in L-shaped grid graphs