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

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