Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420504 | Discrete Applied Mathematics | 2008 | 21 Pages |
Abstract
We consider the pp-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 pp-center problems based on solving covering problems and searching over special domains.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J. Puerto, A. Tamir, J.A. Mesa, D. Pérez-Brito,