On the hardness of labeled correlation clustering problem: a parameterized complexity view
DOI10.1016/J.TCS.2015.03.021zbMATH Open1332.68084OpenAlexW2007201646MaRDI QIDQ896155FDOQ896155
Authors: Xianmin Liu, Hong Gao, 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Aggregating inconsistent information: ranking and clustering
- Algorithms and complexity results for labeled correlation clustering problem
- Approximation algorithms and hardness results for labeled connectivity problems
- Approximation and hardness results for label cut and related problems
- Clustering with qualitative information
- Correlation clustering
- Correlation clustering in general weighted graphs
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Improved bounds on Bell numbers and on moments of sums of random variables
- Local search for the minimum label spanning tree problem with bounded color classes.
- On the complexity of \(k\)-SAT
- Parametrized complexity theory.
- The parameterized complexity of some minimum label problems
- Which problems have strongly exponential complexity?
Cited In (3)
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)
