Longest (s, t)-paths in L-shaped grid graphs. (4th July 2019) - Keshavarz-Kohjerdi, Fatemeh; Bagheri, Alireza
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.