Center location problems on tree graphs with subtree-shaped customers |
| |
Authors: | J Puerto JA Mesa |
| |
Institution: | a Facultad de Matemáticas, Universidad de Sevilla, Spain b School of Mathematical Sciences, Tel Aviv University, Israel c ETS Ingenieros, Universidad de Sevilla, Spain d ETS Ingeniería Informática, Universidad de La Laguna, Spain |
| |
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 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. |
| |
Keywords: | Facility location Subtree-shaped customers Tree graphs |
本文献已被 ScienceDirect 等数据库收录! |
|