An approximation algorithm for the longest path problem in solid grid graphs
From MaRDI portal
Publication:2815541
DOI10.1080/10556788.2015.1130130zbMath1357.68297OpenAlexW2570242489MaRDI QIDQ2815541
Alireza Bagheri, Asghar Asgharian Sardroud
Publication date: 29 June 2016
Published in: Optimization Methods and Software (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/10556788.2015.1130130
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (4)
Off-line exploration of rectangular cellular environments with a rectangular obstacle ⋮ Unit-length rectangular drawings of graphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs
Cites Work
- Unnamed Item
- An approximation algorithm for the longest cycle problem in solid 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
- On computing a longest path in a tree
- ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
- Multi-dimensional labelling approaches to solve the linear fractional elementary shortest path problem with time windows
- Approximating Longest Cycles in Graphs with Bounded Degrees
- Color-coding
- Finding a Path of Superlogarithmic Length
- Finding a Longest Path in a Complete Multipartite Digraph
- Hamilton Paths in Grid Graphs
- A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
- Dynamic programming approaches to solve the shortest path problem with forbidden paths
- Finding Paths and Cycles of Superpolylogarithmic Length
This page was built for publication: An approximation algorithm for the longest path problem in solid grid graphs
