An approximation algorithm for the longest path problem in solid grid graphs. (3rd May 2016)

• Record Type: Journal Article
• Authors: Asgharian Sardroud, Asghar; Bagheri, Alireza
• Is Part Of: Optimization methods and software. Volume 31:Number 3(2016)
• Page Start: 479
• Page End: 493
• Publication Date: 2016-05-03
• Subjects: longest path -- Hamiltonian path -- approximation algorithm -- solid grid graph; 68R10 -- 05C85; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2015.1130130
• Languages: English
• ISSNs: 1055-6788

Abstract

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.