Correlation clustering with vertex splitting

DOI10.4230/LIPICS.SWAT.2024.8MaRDI QIDQ6891149zbMATH OpenFDO

Authors Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, Blair D. Sullivan

Publication date 2 December 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SWAT.2024.8

zbMATH Keywords

approximationcluster editinggraph modificationoverlapping clusteringparameterized complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A 2k kernel for the cluster editing problem
• A golden ratio parameterized algorithm for cluster editing
• Cluster editing with vertex splitting
• Clustering with qualitative information
• Correlation clustering
• Correlation clustering in general weighted graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Handling correlated rounding error via preclustering: a 1.73-approximation for correlation clustering
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the hardness of approximating Multicut and Sparsest-Cut

Cited in

(1)

• On the complexity of establishing hereditary graph properties via vertex splitting

This page was built for publication: Correlation clustering with vertex splitting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6891149)