Article
Center location problems on tree graphs with subtree-shaped customers
Author/s | Puerto Albandoz, Justo
Tamir, Arie Mesa López-Colmenar, Juan Antonio Pérez Brito, Dionisio |
Department | Universidad de Sevilla. Departamento de Estadística e Investigación Operativa |
Publication Date | 2008-08-06 |
Deposit Date | 2022-11-03 |
Published in |
|
Abstract | We consider the p-center problem on tree graphs where the customers are modeled as continua subtrees. We address unweighted and weighted models as well as distances with and without addends. We prove that a relatively ... We consider the p-center problem on tree graphs where the customers are modeled as continua subtrees. We address unweighted and weighted models as well as distances with and without addends. We prove that a relatively simple modification of Handler’s classical linear time algorithms for unweighted 1- and 2-center problems with respect to point customers, linearly solves the unweighted 1- and 2-center problems with addends of the above subtree customer model. We also develop polynomial time algorithms for the p-center problems based on solving covering problems and searching over special domains. |
Citation | Puerto Albandoz, J., Tamir, A., Mesa López-Colmenar, J.A. y Pérez Brito, D. (2008). Center location problems on tree graphs with subtree-shaped customers. Discrete Applied Mathematics, 156 (15), 2890-2910. https://doi.org/10.1016/j.dam.2007.11.022. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Center location problems on tree ... | 668.3Kb | [PDF] | View/ | |