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

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

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) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Parameterized complexity of completeness reasoning for conjunctive queries

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