An exact combinatorial algorithm for minimum graph bisection
An exact combinatorial algorithm for minimum graph bisection
复制标题
DOI：
10.1007/s10107-014-0811-z
复制
发表时间：
2014-09
影响因子：
2.7
通讯作者：
Daniel Delling;Daniel Fleischman;A. Goldberg;Ilya P. Razenshteyn;Renato F. Werneck
中科院分区：
文献类型：
--
作者：
Daniel Delling;Daniel Fleischman;A. Goldberg;Ilya P. Razenshteyn;Renato F. Werneck
我们针对最小图二分问题提出了一种新颖的精确算法，其目标是将图划分为两个大小相等的单元，同时最小化它们之间的边数。我们的算法基于分支定界框架，与大多数以前的方法不同，它是完全组合的。我们引入了基于打包树的新颖下界，以及一种新的分解技术，该技术可以收缩图的整个区域，同时保留最优性保证。我们的算法在最小二等分相对较小的图上效果特别好，首次解决了几个大型现实世界实例（多达数百万个顶点）的最优问题。
We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We introduce novel lower bounds based on packing trees, as well as a new decomposition technique that contracts entire regions of the graph while preserving optimality guarantees. Our algorithm works particularly well on graphs with relatively small minimum bisections, solving to optimality several large real-world instances (with up to millions of vertices) for the first time.