Article ID: | iaor20073391 |
Country: | Netherlands |
Volume: | 150 |
Issue: | 1 |
Start Page Number: | 65 |
End Page Number: | 78 |
Publication Date: | Mar 2007 |
Journal: | Annals of Operations Research |
Authors: | Lari Isabella, Storchi Giovanni, Scozzari Andrea, Becker Ronald I. |
Keywords: | networks: path, location |
In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of