An approximation algorithm for the longest path problem in solid grid graphs
DOI10.1080/10556788.2015.1130130zbMATH Open1357.68297OpenAlexW2570242489MaRDI QIDQ2815541FDOQ2815541
Authors: Asghar Asgharian Sardroud, Alireza Bagheri 
Publication date: 29 June 2016
Published in: Optimization Methods \& Software (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/10556788.2015.1130130
Recommendations
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Paths and cycles (05C38)
Cites Work
- On computing a longest path in a tree
- An approximation algorithm for the longest cycle problem in solid grid graphs
- On computing longest paths in small graph classes
- 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
- Finding Paths and Cycles of Superpolylogarithmic Length
- 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
- Dynamic programming approaches to solve the shortest path problem with forbidden paths
- Title not available (Why is that?)
- Multi-dimensional labelling approaches to solve the linear fractional elementary shortest path problem with time windows
Cited In (12)
- An approximation algorithm for the longest cycle problem in solid grid graphs
- Longest-edge \(n\)-section algorithms: properties and open problems
- Approximating the longest paths in grid graphs
- A linear-time algorithm for the longest path problem in rectangular grid graphs
- The Hamiltonian connectivity of rectangular supergrid graphs
- Longest (s, t)-paths in L-shaped grid graphs
- On approximating the longest path in a graph
- Unit-length rectangular drawings of graphs
- On exact solution approaches for the longest induced path problem
- The longest path problem in odd-sized \(O\)-shaped grid graphs
- Hamiltonian (s, t)-paths in solid supergrid graphs
- Off-line exploration of rectangular cellular environments with a rectangular obstacle
This page was built for publication: An approximation algorithm for the longest path problem in solid grid graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2815541)
