On the Parameterized Complexity of Computing Graph Bisections
On the Parameterized Complexity of Computing Graph Bisections
复制标题
关于计算图二等分的参数化复杂度
DOI：
10.1007/978-3-642-45043-3_8
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
O. Suchý
中科院分区：
文献类型：
--
作者：
René van Bevern;A. Feldmann;Manuel Sorge;O. Suchý
二分问题要求将图的顶点划分为两个相等大小的集合，同时最小化切割大小。这是连接两个顶点集的边数。二分法在过去已被深入研究。然而，只有很少的结果已经公布，考虑这个问题的参数化的复杂性。
The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been thoroughly studied in the past. However, only few results have been published that consider the parameterized complexity of this problem.