论文标题
确切的Treedeppth问题的算法
An Algorithm for the Exact Treedepth Problem
论文作者
论文摘要
我们提出了一种最小深度消除树问题的新型算法，该算法等同于最佳的Treedepepth分解问题。我们的算法利用了两个廉价计算的下限功能，以修剪搜索树，以及破坏对称性和统治规则。我们提出了一项实证研究，表明该算法的表现优于当前最新求解器（基于SAT编码），该算法在一系列图类别上的数量级。
We present a novel algorithm for the minimum-depth elimination tree problem, which is equivalent to the optimal treedepth decomposition problem. Our algorithm makes use of two cheaply-computed lower bound functions to prune the search tree, along with symmetry-breaking and domination rules. We present an empirical study showing that the algorithm outperforms the current state-of-the-art solver (which is based on a SAT encoding) by orders of magnitude on a range of graph classes.
