...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Characterizing acyclic graphs by labeling edges?
【24h】

Characterizing acyclic graphs by labeling edges?

机译：通过标记边缘来表征非循环图？

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

摘要

In this paper two new characterizations of acyclic graphs are introduced. Additionally, restricted versions of them are also proposed to address some important special cases. These restricted characterizations, in turn, were used to obtain new integer programming formulations for some associated relevant NP-hard problems. Resulting formulations are compact, in the sense that the number of variables and constraints they contain are polynomially bounded. One of them, in particular, that for the homogeneous version of the Probabilistic Minimum Spanning Tree Problem, under a MILP solver, is used here to obtain, for the first time, proven optimal solutions to that problem.
机译：本文介绍了无环图的两个新特征。此外，还提出了它们的受限版本以解决一些重要的特殊情况。这些受限制的特征反过来又被用来为一些相关的相关NP-hard问题获得新的整数编程公式。在一定程度上讲，所得公式是紧凑的，因为它们包含的变量和约束的数量是多项式有界的。其中之一，特别是在MILP求解器下的概率最小生成树问题的同质版本中，第一次被使用来证明该问题的最优解。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号