JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]


Journal of Information Science and Engineering, Vol. 29 No. 6, pp. 1109-1120


On the Min-Max 2-Cluster Editing Problem

LI-HSUAN CHEN1, MAW-SHANG CHANG2, CHUN-CHIEH WANG1 AND BANG YE WU1,*
1Department of Computer Science and Information Engineering
National Chung Cheng University
Chiayi, 621 Taiwan
2Department of Computer Science and Information Engineering
Hungkung University
Taichung, 433 Taiwan


    In this paper, we study the problem Min-Max 2-Cluster Editing which asks for a modification of a given graph into two maximal cliques by inserting or deleting edges such that the maximum number k of the editing edges incident to any vertex is minimized. We show the NP-hardness of the problem and present a polynomial-time algorithm when k < n/4, in which n is number of vertices. In addition, we design a 2-approximation algorithm and a branching algorithm for finding an optimal solution. By experiments on random graphs, we show that the exact algorithm is much more efficient than a trivial one.

Keywords: algorithm, clustering editing, graph modification problem, NP-hard, approximation algorithm

  Retrieve PDF document (JISE_201306_03.pdf)