An approximation algorithm for the longest path problem in solid grid graphs. (3rd May 2016) - Asgharian Sardroud, Asghar; Bagheri, Alireza
Abstract : 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 -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.