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

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

zbMATH Keywords

approximation algorithmHamiltonian cyclelongest cyclesolid grid graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

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

This page was built for publication: An approximation algorithm for the longest cycle problem in solid grid graphs