Indirect covering tree problems on spanning tree networks

This paper introduces two types of indirect covering tree problems using a spanning tree as a backbone network. The minimum cost covering subtree seeks the minimum cost collection of arcs that form a subtree and satisfy covering constraints for nodes of the network. Reduction techniques that have been used to solve the location set covering problem are extended to solve the Minimum Cost Covering Subtree. The second problem, The Maximal Indirect Covering Subtree, chooses that subtree which maximizes the demand within a distance standard of nodes of the subtree. In addition, some variations of the maximal indirect covering subtree problem are proposed.