An approximation algorithm for the longest path problem in solid grid graphs

DOI10.1080/10556788.2015.1130130MaRDI QIDQ2815541zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmHamiltonian pathsolid grid graphlongest path

Mathematics Subject Classification ID

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)

Recommendations

• 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
• Approximating the longest paths in 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 1391661 (Why is no real title available?)
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Approximating the longest paths in grid graphs
• Color-coding
• Dynamic programming approaches to solve the shortest path problem with forbidden paths
• Finding Paths and Cycles of Superpolylogarithmic Length
• Finding a Longest Path in a Complete Multipartite Digraph
• Finding a Path of Superlogarithmic Length
• Hamilton Paths in Grid Graphs
• Multi-dimensional labelling approaches to solve the linear fractional elementary shortest path problem with time windows
• On approximating the longest path in a graph
• On computing a longest path in a tree
• On computing longest paths in small graph classes

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)