簇图编辑问题的研究进展  

Algorithms for Cluster Editing:A Survey

作　　者：王建新[1] 万茂武[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机科学》2010年第12期8-11,21,共5页Computer Science

基　　金：国家自然科学基金(60773111);国家教育部创新团队资助计划(IRT0661)资助

摘　　要：簇图编辑问题是一个重要的NP-难问题。作为相关性聚类问题的一个特例,它在计算生物等领域有着重要的应用。参数计算理论出现后,参数化的簇图编辑问题逐渐引起了很多人的注意。介绍了求解簇图编辑问题的近似算法、参数算法和它的一些变形,着重分析了参数化簇图编辑问题核心化和FPT算法的最新结果。最后提出了关于该问题的一些研究方向。The Cluster Editing is known to be a very important NP-hard problem.As a special case of Correlation Clustering,it plays a significant role on many fields such as computation biology.After the theory of parameterized comple-xity was brought up,its parameterized version has drawn much attention.We introduced some approximation and parameterized algorithms for this problem and some variants of it,emphasized on the latest results about its kernelization and FPT algorithms.At the end,we presented some further directions for future research.

关 键 词：簇图编辑问题 聚类问题 NP-难 近似算法 参数算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]