Repositorio de producción científica de la Universidad de Sevilla

The continuous and discrete path variance problem on trees

Opened Access The continuous and discrete path variance problem on trees

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Puerto Albandoz, Justo
Ricca, Federica
Scozzari, Andrea
Departamento: Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Fecha: 2009-03
Publicado en: Networks, 53 (2), 221-228.
Tipo de documento: Artículo
Resumen: In this paper we consider the problem of locating path-shaped facilities on a tree minimizing the variance objective function. This kind of objective function is generally adopted in location problems which arise in the public sector applications, such as the location of evacuation routes or mass transit routes. We consider the general case in which a positive weight is assigned to each vertex of the tree and positive real lengths are associated to the edges. We study both the case in which the path is continuous, that is, the end points of the optimal path can be either vertices or points along an edge, and the case in which the path is discrete, that is, the end points of the optimal path must lie in some vertex of the tree. Given a tree with n vertices, for both these problems we provide algorithms with O(n2) time complexity and we extend our results also to the case in which the length of the path is bounded above. Even in this case we provide polynomial algorithms with the same...
[Ver más]
Cita: Puerto Albandoz, J. y Ricca, F. (2009). The continuous and discrete path variance problem on trees. Networks, 53 (2), 221-228.
Tamaño: 229.6Kb
Formato: PDF

URI: http://hdl.handle.net/11441/47844

DOI: 10.1002/net.20284

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones