| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435544 | Theoretical Computer Science | 2016 | 11 Pages |
Abstract
Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP-complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied. For the two parameterized problems which are fixed-parameter-tractable, the lower bounds of them are analyzed under SETH (Strong Exponential Time Hypothesis).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xianmin Liu, Jianzhong Li, Hong Gao,