An approximation algorithm for the longest cycle problem in solid grid graphs
From MaRDI portal
Publication:266791
DOI10.1016/j.dam.2015.10.022zbMath1333.05091arXiv1502.07085OpenAlexW2962700727MaRDI QIDQ266791
Alireza Bagheri, Asghar Asgharian Sardroud
Publication date: 7 April 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.07085
Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)
Related Items
Off-line exploration of rectangular cellular environments with a rectangular obstacle, Longest (s, t)-paths in L-shaped grid graphs, The longest cycle problem is polynomial on interval graphs, The Hamiltonian connectivity of rectangular supergrid graphs, An approximation algorithm for the longest path problem in solid grid graphs
Cites Work
- Unnamed Item
- 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
- The Longest Path Problem Is Polynomial on Interval Graphs
- Approximating Longest Cycles in Graphs with Bounded Degrees
- Finding Long Paths, Cycles and Circuits
- 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
- Automata, Languages and Programming
- Automata, Languages and Programming
- Algorithms and Computation