Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions

DOI10.1007/s00453-014-9874-8zbMath1328.68098arXiv1303.6867MaRDI QIDQ494805

Bang Ye Wu, Li-Hsuan Chen

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1303.6867

zbMATH Keywords

clustering; kernelization; parameterized algorithm; graph modification; cluster graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem, Parameterized algorithms for min-max 2-cluster editing, Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \(2k\) kernel for the cluster editing problem
• Graph-based data clustering with overlaps
• Exact exponential algorithms.
• Correlation clustering
• Cluster editing with locally bounded modifications
• On the approximation of correlation clustering and consensus clustering
• Fixed-parameter enumerability of cluster editing and related problems
• Fixed-parameter algorithms for cluster vertex deletion
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• A general method to speed up fixed-parameter-tractable algorithms
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Even faster parameterized cluster deletion and cluster editing
• Clustering with qualitative information
• On the notion of balance of a signed graph
• Tight bounds for parameterized complexity of Cluster Editing
• Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms
• Optimal Edge Deletions for Signed Graph Balancing
• Aggregating inconsistent information