• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Branch decomposition heuristics for linear matroids
【24h】

Branch decomposition heuristics for linear matroids

机译：线性拟阵的分支分解试探法

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

摘要

This paper presents three new heuristics which utilize classification, max-flow, and matroid intersection algorithms respectively to derive near-optimal branch decompositions for linear matroids. In the literature, there are already excellent heuristics for graphs, however, no practical branch decomposition methods for general linear matroids have been addressed yet. Introducing a "measure" which compares the "similarity" of elements of a linear matroid, this work reforms the linear matroid into a similarity graph. Then, the classification method, the max-flow method, and the mat-flow method, all based on the similarity graph, are utilized on the similarity graph to derive separations for a near-optimal branch decomposition. Computational results using the methods on linear matroid instances are shown respectively.
机译：本文提出了三种新的启发式算法，分别利用分类，最大流和拟阵交集算法来推导线性拟阵的近似最优分支分解。在文献中，已经有极好的图形启发式方法，但是，还没有针对通用线性拟阵的实用分支分解方法。引入一种“度量”来比较线性拟阵的元素的“相似性”，这项工作将线性拟阵拟定为相似图。然后，将所有基于相似度图的分类方法，最大流方法和垫流方法用于相似度图，以得出近似最优分支分解的间隔。分别显示了在线性拟阵实例上使用该方法的计算结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号