When Does Domination Matter? A Structural and Computational Study of Spanning and Dominating Trees in Geometric Networks

In geometric communication networks, a backbone is useful only if it is inexpensive to build and, at the same time, close enough to the demand points it must serve. This paper studies a backbone design problem in geometric communication networks that explicitly captures this trade-off between connectivity and user coverage. Two classical combinatorial optimization paradigms—the minimum spanning tree (MST), which promotes low-cost connectivity, and the dominating tree (DT), which additionally enforces that every node either belongs to the backbone or is adjacent to an active backbone node—are considered. To compare both paradigms within a common framework, this paper proposes a unified mixed-integer optimization model that balances backbone-construction and user-assignment costs. Three classes of exact formulations, namely MTZ, single-flow, and cut-set formulations, are developed. In particular, the single-flow model with valid inequalities and root-aware connectivity cuts is strengthened. For larger instances, the exact approach is complemented with a local branching matheuristic. Finally, theoretical results on computational complexity, formulation structure, and dominance relations between the MST and DT models are provided. Computational experiments show that the single-flow formulation achieves the best scalability. Furthermore, a sensitivity analysis with respect to the communication radius and the weighting parameter α reveals a structural transition: as the network becomes denser or the objective becomes more coverage-oriented, MST and DT solutions tend to converge. The results give a concrete way to identify when domination constraints are worth imposing and when a simpler spanning tree design already captures the relevant structure.