Solving covering problems and the uncapacitated plant location problem on trees |
| |
Authors: | Antoon Kolen |
| |
Affiliation: | Erasmus University, Rotterdam, The Netherlands |
| |
Abstract: | Given a tree network on n vertices, a neighborhood subtree is defined as the set of all points on the tree within a certain radius of a given point, called the center. It is shown that for any two neighborhood subtrees containing the same endpoint of a longest path in the tree one is contained in the other. This result is then used to obtain O(n2) algorithms for the minimum cost covering problem and the minimum cost operating problem as well as an O(n3) algorithm for the uncapacitated plant location problem on the tree. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|