Cluster editing problem for points on the real line: A polynomial time algorithm

作     者：Mannaa, Bassel 

作者机构：Chalmers Univ Technol SE-41296 Gothenburg Sweden 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2010年第110卷第21期

页      面：961-965页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Algorithms Graph algorithms Clustering Dynamic programming 

摘      要：In this paper we consider the cluster editing problem for a special type of graphs, where the vertices represent points on the real line and there is an edge between each two vertices for which the distance between their corresponding points on the line is less than a given constant. We give a polynomial time cluster editing algorithm for this class of graphs. (C) 2010 Elsevier B.V. All rights reserved.