Approximating the longest paths in grid graphs

DOI10.1016/j.tcs.2011.06.010zbMath1222.68089OpenAlexW2047690551MaRDI QIDQ719276

Yong-Jin Liu, Wen-Qi Zhang

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.010

zbMATH Keywords

approximation algorithmgrid graphslong pathssquare-free 2-factor

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Hamiltonian cycles in linear-convex supergrid graphs ⋮ Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths ⋮ 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 ⋮ The Hamiltonian properties of supergrid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Hamiltonian paths in \(L\)-shaped grid graphs ⋮ A genetic algorithm for the picture maze generation problem ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Approximating the Longest Cycle Problem in Sparse Graphs
• Approximating Longest Cycles in Graphs with Bounded Degrees
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• Finding a Path of Superlogarithmic Length
• Circumference of Graphs with Bounded Degree
• Hamilton Paths in Grid Graphs

This page was built for publication: Approximating the longest paths in grid graphs