论文标题
更快的平行多端切割
Faster Parallel Multiterminal Cuts
论文作者
论文摘要
根据Henzinger等人的最新工作，我们为多发裁切问题提供了改进的分支和分支求解器。我们为新的，高效的数据减少规则提供了将图形转换为较小的等效实例。此外，我们提出了一种局部搜索算法，该算法可以显着改善对多次切割问题的给定解决方案。与Henzinger等人的最新算法相比，我们的确切算法能够为更多和更严重的问题提供精确的解决方案。并为超过三分之二的问题提供更好的解决方案，这些问题太大而无法解决最佳。此外，我们提供了一种不精确的启发式算法，该算法在合理的时间内为非常艰难的实例计算高质量的解决方案。
We give an improved branch-and-bound solver for the multiterminal cut problem, based on the recent work of Henzinger et al.. We contribute new, highly effective data reduction rules to transform the graph into a smaller equivalent instance. In addition, we present a local search algorithm that can significantly improve a given solution to the multiterminal cut problem. Our exact algorithm is able to give exact solutions to more and harder problems compared to the state-of-the-art algorithm by Henzinger et al.; and give better solutions for more than two third of the problems that are too large to be solved to optimality. Additionally, we give an inexact heuristic algorithm that computes high-quality solutions for very hard instances in reasonable time.
