Maximal Direct Covering Tree Problems

Concepts of coverage are extended to a problem of network design. Maximal covering tree problems are introduced to widen the applicability of the minimal spanning tree (MST), a classic network design problem, which defines the minimal length connection of all nodes in a network. Maximal covering tree problems relax the restriction that all nodes must be connected. Instead, maximal covering tree problems identify the best choices for subtrees in the spanning tree network based on the relative benefits and costs of connecting nodes. Two-objective integer programming (IP) models are formulated and solved for the maximal direct covering tree (1) on spanning networks in which arcs currently exist and (2) for the general spanning tree graph.