Models for Minimum Cost Dominating Trees

In this work we propose and compare two new models for determining dominating trees (DT) of minimum cost in undirected weighted graphs. One model is based on a new representation of arborescences in digraphs, while the second one is obtained from the generalized spanning tree polytope. Computational results show that our models allow solving instances with up to 100 nodes to optimality, which is not possible to achieve with other models proposed in the literature. © 2016 Elsevier B.V.