Approximating the longest paths in grid graphs

DOI10.1016/J.TCS.2011.06.010MaRDI QIDQ719276zbMATH OpenOpenAlexFDO

Authors Wen-Qi Zhang, Yong-Jin Liu

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)

Recommendations

• An approximation algorithm for the longest path problem in solid grid graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Longest (s, t)-paths in L-shaped grid graphs
• On approximating the longest path in a graph

Cites work

• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• scientific article; zbMATH DE number 1342133 (Why is no real title available?)
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Approximating the Longest Cycle Problem in Sparse Graphs
• Circumference of Graphs with Bounded Degree
• Finding a Path of Superlogarithmic Length
• Hamilton Paths in Grid Graphs
• On approximating the longest path in a graph
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

Cited in

(19)

• 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
• Longest-edge \(n\)-section algorithms: properties and open problems
• On approximating the longest path in a graph
• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
• 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
• Number of Shortest Paths in Triangular Grid for 1- and 2-Neighborhoods
• On approximating the longest path in a graph
• Hamiltonian paths in L-shaped grid graphs
• A genetic algorithm for the picture maze generation problem
• NP-completeness for minimizing maximum edge length in grid embeddings
• Hamiltonian cycles in linear-convex supergrid graphs
• The Hamiltonian properties of supergrid graphs
• The longest path problem in odd-sized O-shaped grid graphs
• On the number of shortest paths by neighborhood sequences on the square grid
• 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: Approximating the longest paths in grid graphs

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