The location of median paths on grid graphs

The location of median paths on grid graphs

0.00 Avg rating0 Votes
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: , , ,
Keywords: networks: path, location
Abstract:

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 O(n) and O(n𝓁) respectively, where n is the number of vertices of the grid and 𝓁 is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.

Reviews

Required fields are marked *. Your email address will not be published.