Longest (s, t)-paths in L-shaped grid graphs. (4th July 2019)

• Record Type: Journal Article
• Authors: Keshavarz-Kohjerdi, Fatemeh; Bagheri, Alireza
• Is Part Of: Optimization methods and software. Volume 34:Number 4(2019)
• Page Start: 797
• Page End: 826
• Publication Date: 2019-07-04
• Subjects: grid graph -- Hamiltonian path -- L-shaped grid graph -- longest path; 05C85 -- 68R10; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1460665
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : The longest path problem, that is, finding a simple path with the maximum number of vertices, is a well-known NP-hard problem with many applications. However, for some classes of graphs, including solid grid graphs and grid graphs with some holes, it is open. An L -shaped grid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we show that a longest path between two given vertices s and t of an L -shaped grid graph can be computed in linear time.