Longest (s, t)-paths in L-shaped grid graphs

Fatemeh Keshavarz-Kohjerdi | Alireza Bagheri

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=85195
Date :  2018/04/19
Publish in :    Optimization Methods and Software
DOI :  https://doi.org/10.1080/10556788.2018.1460665
Link :  https://www.tandfonline.com/doi/abs/10.1080/10556788.2018.1460665
Keywords :L-shaped, graphs

Abstract :

---

The longest path problem, that is, finding a simple path with the maximum number of vertices, is a wellknown 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.