On the hardness of labeled correlation clustering problem: a parameterized complexity view
From MaRDI portal
Publication:896155
DOI10.1016/j.tcs.2015.03.021zbMath1332.68084OpenAlexW2007201646MaRDI QIDQ896155
Hong Gao, Xianmin Liu, Jian-Zhong Li
Publication date: 11 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.021
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation and hardness results for label cut and related problems
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Correlation clustering
- Which problems have strongly exponential complexity?
- Local search for the minimum label spanning tree problem with bounded color classes.
- The parameterized complexity of some minimum label problems
- Algorithms and complexity results for labeled correlation clustering problem
- Approximation algorithms and hardness results for labeled connectivity problems
- Parametrized complexity theory.
- Correlation clustering in general weighted graphs
- Clustering with qualitative information
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Aggregating inconsistent information
- On the complexity of \(k\)-SAT
This page was built for publication: On the hardness of labeled correlation clustering problem: a parameterized complexity view