Efficient solution methods for covering tree problems

In recent years, interest has been shown in the optimal location of ‘extensive’ facilities in a network. Two such problems – the Maximal Direct and Indirect Covering Tree problems – were introduced by Hutson and ReVelle. Previous solution techniques are extended to provide an efficient algorithm for the Indirect Covering Tree problem and the generalization in which demand covered is attenuated by distance. It is also shown that the corresonding problem is NP-hard when the underlying network is not a tree.