On the hardness of labeled correlation clustering problem: a parameterized complexity view

DOI10.1016/J.TCS.2015.03.021MaRDI QIDQ896155zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

lower boundparameterized complexitystrong exponential time hypothesislabeled correlation clustering

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2147947 (Why is no real title available?)
• scientific article; zbMATH DE number 1445322 (Why is no real title available?)
• 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)

• Parameterized complexity of completeness reasoning for conjunctive queries
• On the parameterized complexity of labelled correlation clustering problem
• Algorithms and complexity results for labeled correlation clustering problem

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)