...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>RAIRO Operation Research >HEURISTIC AND METAHEURISTIC METHODS FOR COMPUTING GRAPH TREEWIDTH
【24h】

HEURISTIC AND METAHEURISTIC METHODS FOR COMPUTING GRAPH TREEWIDTH

机译：计算图形宽度的启发式和准方法

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

摘要

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The aim of this paper is to propose two new methods for computing the treewidth of graphs: a heuristic and a meta-heuristic. The heuristic returns good results in a short computation time, whereas the metaheuristic (a Tabu search method) returns the best results known to have been obtained so far for all the DIMACS vertex coloring / treewidth benchmarks (a well-known collection of graphs used for both vertex coloring and treewidth problems.) Our results actually improve on the previous best results for treewidth problems in 53% of the cases. Moreover, we identify properties of the triangulation process to optimize the computing time of our method.
机译：关于NP难题，树宽的概念引起了极大的兴趣。确实，一些研究表明，树分解方法可用于解决树宽有界时多项式时间内的许多基本优化问题，即使对于任意图形而言，计算树宽都是NP难的。几篇论文介绍了启发式计算实验。对于许多图形，启发式结果与最佳下限之间的差异仍然很大。本文的目的是提出两种计算图树宽的新方法：启发式算法和元启发式算法。启发式算法在较短的计算时间内返回了良好的结果，而元启发式算法（禁忌搜索法）则返回了迄今为止对于所有DIMACS顶点着色/树宽基准（已知的用于包括顶点着色和树宽问题。）在53％的情况下，我们的结果实际上比以前对树宽问题的最佳结果有所改善。此外，我们确定三角剖分过程的属性，以优化我们方法的计算时间。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号