Partitioning planar graphs: a fast combinatorial approach for max-cut
Partitioning planar graphs: a fast combinatorial approach for max-cut
复制标题
DOI：
10.1007/s10589-010-9335-5
复制
发表时间：
2012
影响因子：
2.2
通讯作者：
F. Liers;G. Pardella
中科院分区：
文献类型：
--
作者：
F. Liers;G. Pardella
最大割问题要求将一个图G =（V，E）的节点V划分为两个集合（其中一个集合可能为空），使得连接不同划分中节点的边的权和最大。而对于一般情况下的最大割问题是NP-困难的，它是多项式可解的某些类的图。对于平面图，有几个多项式时间的方法来确定任意选择边权的最大割。通常，该问题通过计算某个关联图中的最小权重完美匹配来解决。最有效的已知算法是Shih等人（IEEE Trans. Comput. 39（5）：694-697，1990）和Berman等人的方法（WADS，Lecture Notes in Computer Science，vol.1663，pp.25 -36，Springer，柏林，1999）。前者的运行时间可以由。后一种算法更一般地用于确定图中的T连接。虽然它在运行时间上有一个稍微大一点的界限，其中α（|V|）是Ackermann函数的逆函数，在实际应用中可以解决大的问题.本文提出了一种新的确定任意加权平面图的最大割的简单算法.它的运行时间是有界的，同样的界限实现了Shih等人。它可以很容易地确定最大的削减在巨大的随机以及现实世界的图与多达106个节点。我们目前的实验结果，我们的方法使用两种不同的匹配实现。我们进一步比较我们的方法与Shih等人。和Berman等人。事实证明，我们的算法是相当快的，在实践中比Shih等人。此外，它产生一个更小的关联图。其扩展图的大小与Berman等人的扩展图的大小相当。然而，尽管Berman等人生成扩展图的过程非常复杂（因此需要复杂的实现），但实现我们的方法是一项简单而直接的任务。
Themax-cutproblem asks for partitioning the nodesVof a graphG=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances themax-cutproblem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput. 39(5):694–697, 1990) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25–36, Springer, Berlin, 1999). The running time of the former can be bounded by. The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of, whereα(|V|) is the inverse Ackermann function, it can solve large instances in practice.In this work, we present a new and simple algorithm for determining maximum cuts for arbitrary weighted planar graphs. Its running time is bounded by, the same bound achieved by Shih et al. It can easily determine maximum cuts in huge random as well as real-world graphs with up to 106nodes. We present experimental results for our method using two different matching implementations. We furthermore compare our approach with those of Shih et al. and Berman et al. It turns out that our algorithm is considerably faster in practice than Shih et al. Moreover, it yields a much smaller associated graph. Its expanded graph size is comparable to that of Berman et al. However, whereas the procedure of generating the expanded graph in Berman et al. is very involved (thus needs a sophisticated implementation), implementing our approach is an easy and straightforward task.