...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm
【24h】

The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm

机译：最小度约束的最小生成树问题：公式和分支剪切算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Given an edge weighted undirected graph G and a positive integer d, the Min-Degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree of G, such that each vertex is either a leaf or else has degree at least d in the tree. In this paper, we discuss two formulations for MDMST based on exponentially many undirected and directed subtour breaking constraints and compare the strength of their Linear Programming (LP) bounds with other bounds in the literature. Aiming to overcome the fact that the strongest of the two models, the directed one, is not symmetric with respect to the LP bounds, we also presented a symmetric compact reformulation, devised with the application of an Intersection Reformulation Technique to the directed model. The reformulation proved to be much stronger than the previous models, but evaluating its bounds is very time consuming. Thus, better computational results were obtained by a Branch-and-cut algorithm based on the original directed formulation. With the proposed method, several new optimality certificates and new best upper bounds for MDMST were provided.
机译：给定一个边缘加权无向图G和一个正整数d，最小度约束最小生成树问题（MDMST）包括找到G的最小代价生成树，这样每个顶点要么是叶子，要么至少具有度数d在树上。在本文中，我们讨论了基于指数式许多无向和有向子旅行中断约束的MDMST公式，并比较了它们的线性规划（LP）界限与文献中其他界限的强度。为了克服以下事实：两个模型中最强的一个（有向模型）相对于LP边界不对称，我们还提出了一种对称紧致的重新设计，是通过将交叉点重新设置技术应用于有向模型而设计的。事实证明，重新制定比以前的模型要强大得多，但是评估其界限非常耗时。因此，基于原始有向公式的分支剪切算法获得了更好的计算结果。通过提出的方法，为MDMST提供了一些新的最优性证书和新的最佳上限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号