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

作者：Sardroud Asghar Asgharian; Bagheri Alireza^*

来源：Optimization Methods and Software, 2016, 31(3): 479-493.

DOI：10.1080/10556788.2015.1130130

• longest path
• Hamiltonian path
• approximation algorithm
• solid grid graph
• 68R10
• 05C85

The longest path problem is a well-known NP-hard problem which can be used to model and solve some optimization problems. There are only a few classes of graphs for which this problem can be solved polynomially. In addition, the results show that the problem is hard to approximate within any reasonable factor for general graphs. We introduce a polynomial-time 2/3-approximation algorithm for the longest path problem in solid grid graphs. Our algorithm can also approximate the longest path between any two given boundary vertices of a solid grid graph within the same approximation factor.

• 出版日期2016-6