The location of median paths on grid graphs |
| |
Authors: | Ronald I. Becker Isabella Lari Andrea Scozzari Giovanni Storchi |
| |
Affiliation: | (1) Department of Mathematics, University of Cape Town, Rondebosh, 7700, South Africa;(2) Dipartimento di Statistica, Probabilità e Statistiche Applicate, Università di Roma “La Sapienza”, P.le A. Moro 5, 00185 Roma, Italy;(3) Dipartimento Matematica per le Decisioni Economiche, Finanziarie ed Assicurative, Università di Roma “La Sapienza”, Via del Castro Laurenziano 9, 00161 Roma, Italy |
| |
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. |
| |
Keywords: | Median paths Grid graphs Facility location |
本文献已被 SpringerLink 等数据库收录! |
|