Maximal covering tree problem

Hutson and ReVelle define the maximal direct covering tree problem as a bicriterion problem to identify a subtree of a given tree. The two criteria are to maximize demand covered by the subtree and to minimize the cost of the subtree. Demand at a node on the underlying tree is considered covered if it is within some prespecified covering distance S of the subtree. In the direct covering version of the problem, S=0. In this article the authors present a new bicriterion formulation of the maximal direct covering tree problem and present O(n²) algorithms for solving both this problem and the special case where one must add to an existing subtree. The new formulation is extremely concise; consequently, additional constraints may be added where appropriate. This is demonstrated with the addition of a budget constraint. In addition, the authors demonstrate that the new formulation and algorithm can be readily extended to incorporate indirect covering (i.e., S>0) as defined by Kim et al.