On the hardness of labeled correlation clustering problem: a parameterized complexity view
DOI10.1016/J.TCS.2015.03.021zbMATH Open1332.68084OpenAlexW2007201646MaRDI QIDQ896155FDOQ896155
Hong Gao, Xianmin Liu, Jianzhong 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
Recommendations
- On the parameterized complexity of labelled correlation clustering problem
- Algorithms and complexity results for labeled correlation clustering problem
- A note on the inapproximability of correlation clustering
- Approximation algorithms for two variants of correlation clustering problem
- Approximation algorithms for the lower bounded correlation clustering problem
- Approximation algorithms for the capacitated correlation clustering problem with penalties
- On the approximation of correlation clustering and consensus clustering
- Approximation algorithm for the capacitated correlation clustering problem with penalties
- Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem
- On the complexity of clustering with relaxed size constraints in fixed dimension
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Clustering with qualitative information
- Aggregating inconsistent information
- Correlation clustering
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of \(k\)-SAT
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- The parameterized complexity of some minimum label problems
- Approximation algorithms and hardness results for labeled connectivity problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Correlation clustering in general weighted graphs
- Local search for the minimum label spanning tree problem with bounded color classes.
- Approximation and hardness results for label cut and related problems
- Algorithms and complexity results for labeled correlation clustering problem
Cited In (1)
This page was built for publication: On the hardness of labeled correlation clustering problem: a parameterized complexity view
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896155)
