The longest path problem in odd-sized O-shaped grid graphs
DOI10.1142/S0129054123500065MaRDI QIDQ6492015FDOQ6492015
Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri
Publication date: 24 April 2024
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Hamiltonian pathgrid graphlongest pathodd-sized \(O\)-shaped grid graphsrectangular grid graph with a rectangular hole
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)
Cites Work
- Survey on path and cycle embedding in some networks
- ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
- The Longest Path Problem Is Polynomial on Interval Graphs
- Finding a Longest Path in a Complete Multipartite Digraph
- Hamilton Paths in Grid 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
- A note on cycle embedding in hypercubes with faulty vertices
- An efficient algorithm for constructing Hamiltonian paths in meshes
- On Hamiltonian cycles and Hamiltonian paths
- Hamiltonian paths in \(L\)-shaped grid graphs
- Algorithms for long paths in graphs
- The longest path problem is polynomial on cocomparability graphs
- An approximation algorithm for the longest path problem in solid grid graphs
- A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs
- A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole
- Longest (s, t)-paths in L-shaped grid graphs
- Title not available (Why is that?)
- Off-line exploration of rectangular cellular environments with a rectangular obstacle
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)
