A Complete Anytime Algorithm for Treewidth
A Complete Anytime Algorithm for Treewidth
复制标题
树宽的完整随时算法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
R. Dechter
中科院分区：
文献类型：
--
作者：
Vibhav Gogate;R. Dechter
在本文中，我们提出了一种称为QuickBB的分支和绑定算法，用于计算无向图的树宽。该算法在图形顶点的完美消除顺序中进行搜索。该算法使用新颖的修剪和传播技术，这些技术源自图未成年人的理论和图形同构。我们提出了一种称为次要宽度的新算法，用于计算在分支和结合算法中使用的树宽的下限，并改善了早期可用的下限。在图形着色和贝叶斯网络中随机生成的图形和基准测试上对QuickBb的经验评估表明，它始终比Quick-Tree [Shoikhet and Geiger，1997]等完整算法更好。 QuickBB在任何时间的性能中也具有良好的性能，能够在某些图的树宽上产生更好的上限，这些图形无法迄今无法计算出最佳的树宽。
In this paper, we present a Branch and Bound algorithm called QuickBB for computing the treewidth of an undirected graph. This algorithm performs a search in the space of perfect elimination ordering of vertices of the graph. The algorithm uses novel pruning and propagation techniques which are derived from the theory of graph minors and graph isomorphism. We present a new algorithm called minor-min-width for computing a lower bound on treewidth that is used within the branch and bound algorithm and which improves over earlier available lower bounds. Empirical evaluation of QuickBB on randomly generated graphs and benchmarks in Graph Coloring and Bayesian Networks shows that it is consistently better than complete algorithms like Quick-Tree [Shoikhet and Geiger, 1997] in terms of cpu time. QuickBB also has good anytime performance, being able to generate a better upper bound on treewidth of some graphs whose optimal treewidth could not be computed up to now.