Exact Algorithms for Cluster Editing: Evaluation and Experiments
Exact Algorithms for Cluster Editing: Evaluation and Experiments
复制标题
DOI：
10.1007/s00453-009-9339-7
复制
发表时间：
2011-06-01
期刊：
影响因子：
1.1
通讯作者：
Klau, Gunnar W.
中科院分区：
文献类型：
--
作者：
Boecker, Sebastian;Briesemeister, Sebastian;Klau, Gunnar W.
群集编辑问题定义如下：给定无环形图，我们希望找到一组最小基数的边缘修改（插入和删除），以便修改的图形由不相关的群集组成。我们提供了此类经验结果。使用固定参数算法和线性编程的精确方法的问题。我们研究了独立于参数的数据减少方法，并发现如果边缘修改的数量k小于垂直杆V垂直条的某些倍数，则有效的预处理是可能的，其中v是输入图的顶点集。特别是，将参数依赖性数据降低与上限和上限相结合，我们可以有效地减少满足K的图形
The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques.We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of vertical bar V vertical bar , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying k