The Library
Tight bounds for parameterized complexity of cluster editing with a small number of clusters
Tools
Tools
Tools
Fomin, Fedor V., Kratsch, Stefan, Pilipczuk, Marcin, Pilipczuk, Michał and Villanger, Yngve (2014) Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Journal of Computer and System Sciences, Volume 80 (Number 7). pp. 1430-1447. doi:10.1016/j.jcss.2014.04.015
|
PDF
WRAP_1371795-cs-270115-clustering.pdf - Requires a PDF viewer. Download (565Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jcss.2014.04.015
Abstract
In the Cluster Editing problem, also known as Correlation Clustering, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k edges. We give a subexponential-time parameterized algorithm that in time View the MathML source decides whether G can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. Our algorithmic findings are complemented by the following tight lower bound on the asymptotic behavior of our algorithm. We show that unless ETH fails, for any constant 0<σ≤1, there is p=Θ(kσ) such that there is no algorithm deciding in time View the MathML source whether G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies.
| Item Type: | Journal Article | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||||
| Library of Congress Subject Headings (LCSH): | Cluster analysis, Graph theory | ||||||||||
| Journal or Publication Title: | Journal of Computer and System Sciences | ||||||||||
| Publisher: | Academic Press | ||||||||||
| ISSN: | 0022-0000 | ||||||||||
| Official Date: | November 2014 | ||||||||||
| Dates: |
|
||||||||||
| Volume: | Volume 80 | ||||||||||
| Number: | Number 7 | ||||||||||
| Page Range: | pp. 1430-1447 | ||||||||||
| DOI: | 10.1016/j.jcss.2014.04.015 | ||||||||||
| Status: | Peer Reviewed | ||||||||||
| Publication Status: | Published | ||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||
| Funder: | Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC), Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Netherlands Organisation for Scientific Research] (NWO), Narodowe Centrum Nauki (NCN), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP) | ||||||||||
| Grant number: | 267959 (ERC), N206 567140 (NCN) | ||||||||||
| Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
