The Multi-parameterized Cluster Editing Problem
The Multi-parameterized Cluster Editing Problem
复制标题
多参数化聚类编辑问题
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
F. Abu
中科院分区：
文献类型：
--
作者：
F. Abu
簇编辑问题寻求通过最小数量的边编辑操作将给定的无向图转换为传递图。现有的算法往往表现出缓慢的性能，并可能提供集群没有实际意义，如单例。引入了一个受约束的聚类编辑版本，具有更多的输入参数，这些参数设置了聚类大小的下限以及每个顶点的边添加和删除量的上限。当每个顶点的边编辑操作小于最小簇大小的一半时，新的公式允许我们在多项式时间内（精确地）解决簇编辑。此外，我们解决的情况下，新的边缘添加和删除边界（每个顶点）是小常数。我们表明，在这种情况下，集群编辑有一个线性大小的内核。
The Cluster Editing problem seeks a transformation of a given undirected graph into a transitive graph via a minimum number of edge-edit operations. Existing algorithms often exhibit slow performance and could deliver clusters of no practical significance, such as singletons. A constrained version of Cluster Editing is introduced, featuring more input parameters that set a lower bound on the size of a clique-cluster as well as upper bounds on the amount of both edge-additions and deletions per vertex. The new formulation allows us to solve Cluster Editing (exactly) in polynomial time when edge-edit operations per vertex is smaller than half the minimum cluster size. Moreover, we address the case where the new edge addition and deletion bounds (per vertex) are small constants. We show that Cluster Editing has a linear-size kernel in this case.