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

DOI10.1016/J.DAM.2015.10.022MaRDI QIDQ266791zbMATH OpenOpenAlexFDO

Authors Asghar Asgharian Sardroud, Alireza Bagheri

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

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

Abstract: Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least $frac2n3+1$ in 2-connected $n$-node solid grid graphs. Keywords: Longest cycle, Hamiltonian cycle, Approximation algorithm, Solid grid graph.

Recommendations

• An approximation algorithm for the longest path problem in solid grid graphs
• Approximating the longest paths in grid graphs
• Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Computing and Combinatorics

Cites work

• 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
• Algorithms and Computation
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Approximating the longest paths in grid graphs
• Automata, Languages and Programming
• Automata, Languages and Programming
• Color-coding
• Finding Long Paths, Cycles and Circuits
• Finding Paths and Cycles of Superpolylogarithmic Length
• Finding a Longest Path in a Complete Multipartite Digraph
• Finding a Path of Superlogarithmic Length
• Finding large cycles in Hamiltonian graphs
• Hamilton Paths in Grid Graphs
• On approximating the longest path in a graph
• 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

Cited in

(10)

• The longest cycle problem is polynomial on interval graphs
• Approximating the longest paths in grid graphs
• Exact Solution Algorithms for the Chordless Cycle Problem
• ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• The Hamiltonian connectivity of rectangular supergrid graphs
• Longest (s, t)-paths in L-shaped grid graphs
• Approximating the Longest Cycle Problem in Sparse Graphs
• Hamiltonian (s, t)-paths in solid supergrid graphs
• Off-line exploration of rectangular cellular environments with a rectangular obstacle
• An approximation algorithm for the longest path problem in solid grid graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266791)