Models for minimum cost dominating trees

详细信息    查看全文

• 作者：Pablo Adasme ^{pablo.adasme@usach.cl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：dominating tree ; compact model ; generalized spanning tree polytope
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：52
• 期：Complete
• 页码：101-107
• 全文大小：196 K

文摘

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.