Name
Abstract | ||
|---|---|---|
The goal of the cluster editing problem is to add or delete a minimum number of edges from a given graph, so that the resulting graph becomes a union of disjoint cliques. The cluster editing problem is closely related to correlation clustering and has applications, e.g. in image segmentation. For general graphs this problem is APX-hard. In this paper we present an efficient polynomial time approximation scheme for the cluster editing problem on graphs embeddable in the plane with a few edge crossings. The running time of the algorithm is 2(O)(epsilon(-1) log(epsilon(-1)))(n) for planar graphs and 2(O)(k(2) epsilon(-1) log(k(2) epsilon(-1)))(n) for planar graphs with at most k crossings. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-51741-4_3 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Graph approximation,Correlation clustering,Cluster editing,PTAS,k-planarity,Microscopy cell segmentation | Discrete mathematics,Graph,Mathematical optimization,Combinatorics,Disjoint sets,Correlation clustering,Image segmentation,Planar graph,Polynomial-time approximation scheme,Mathematics | Conference |
Volume | ISSN | Citations |
10138 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| André Berger | 1 | 81 | 7.59 |
| Alexander Grigoriev | 2 | 203 | 24.23 |
| Andrej Winokurow | 3 | 2 | 0.72 |