The longest path problem in odd-sized O-shaped grid graphs

DOI10.1142/S0129054123500065MaRDI QIDQ6492015zbMATH OpenFDO

Authors Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Publication date 24 April 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian pathgrid graphlongest pathodd-sized \(O\)-shaped grid graphsrectangular grid graph with a rectangular hole

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• Longest (s, t)-paths in L-shaped grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• 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
• Hamiltonian paths in \(L\)-shaped grid graphs

Cites work

• scientific article; zbMATH DE number 2086688 (Why is no real title available?)
• A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• A note on cycle embedding in hypercubes with faulty vertices
• A polynomial time algorithm for longest paths in biconvex graphs
• Algorithms for long paths in graphs
• An approximation algorithm for the longest path problem in solid grid graphs
• An efficient algorithm for constructing Hamiltonian paths in meshes
• Approximating the longest paths in grid graphs
• Finding a Longest Path in a Complete Multipartite Digraph
• Hamilton Paths in Grid Graphs
• Hamiltonian paths in \(L\)-shaped grid graphs
• Longest (s, t)-paths in L-shaped grid graphs
• Off-line exploration of rectangular cellular environments with a rectangular obstacle
• On Hamiltonian cycles and Hamiltonian paths
• On approximating the longest path in a graph
• On computing longest paths in small graph classes
• Survey on path and cycle embedding in some networks
• The Longest Path Problem Is Polynomial on Interval Graphs
• The longest path problem is polynomial on cocomparability graphs

This page was built for publication: The longest path problem in odd-sized \(O\)-shaped grid graphs

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