Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees

摘要

In this paper we consider the problem of locating a path-shaped or tree-shaped (extensive) facility in trees under the condition that existing facilities are already located. We introduce a parametric-pruning method to solve the conditional extensive weighted 1-center location problems in trees in linear time. This improves the recent results of O(n log n) by Tamir et al.