@inbook{07f97f7b77d14563a30f9532af887a1b,
title = "A PTAS for the Cluster Editing Problem on Planar Graphs",
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 apx{\mathbb {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(? -1 log(? -1 )) n 2o(?-1log?(?-1))n{2^{o\left( \epsilon ^{-1} \log (\epsilon ^{-1})\right) }n} for planar graphs and 2 o(k 2 ? -1 log(k 2 ? -1 )) n 2o(k2?-1log?(k2?-1))n2^{o\left( k^2\epsilon ^{-1}\log \left( k^2\epsilon ^{-1}\right) \right) }n for planar graphs with at most k crossings.",
keywords = "Graph approximation, Correlation clustering, Cluster editing, PTAS, k-planarity, Microscopy cell segmentation",
author = "Andre Berger and Alexander Grigoriev and Andrej Winokurow",
note = "NO DATA USED",
year = "2017",
month = jan,
day = "7",
doi = "10.1007/978-3-319-51741-4_3",
language = "English",
isbn = "978-3-319-51740-7",
volume = "10138",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "27--39",
booktitle = "Approximation and Online Algorithms",
address = "United States",
edition = "Lecture Notes in Computer Science",
}