Name
Title | ||
|---|---|---|
On the hardness of labeled correlation clustering problem: A parameterized complexity view. |
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). |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.03.021 | Theoretical Computer Science |
Keywords | Field | DocType |
Labeled correlation clustering,Parameterized complexity,Lower bound,Strong Exponential Time Hypothesis | Discrete mathematics,Combinatorics,Parameterized complexity,Correlation clustering,Upper and lower bounds,Mathematics,Exponential time hypothesis | Journal |
Volume | Issue | ISSN |
609 | P3 | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xianmin Liu | 1 | 12 | 5.00 |
| Jianzhong Li | 2 | 3196 | 304.46 |
| Hong Gao | 3 | 1086 | 120.07 |