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

作者：Sardroud Asghar Asgharian; Bagheri Alireza^*

来源：Discrete Applied Mathematics, 2016, 204: 6-12.

DOI：10.1016/j.dam.2015.10.022

• Longest cycle
• Hamiltonian cycle
• Approximation algorithm
• Solid grid graph

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 2n/3 + 1 in 2-connected n-node solid grid graphs.

• 出版日期2016-5-11