On the parameterized complexity of consensus clustering

DOI10.1016/j.tcs.2014.05.002zbMath1360.68506OpenAlexW2029303541MaRDI QIDQ2015135

Christian Komusiewicz, Jiong Guo, Mathias Weller, Martin Dörnfelder

Publication date: 23 June 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.05.002

zbMATH Keywords

local searchNP-hard problemdata clusteringsearch tree algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Unnamed Item ⋮ Cluster Editing in Multi-Layer and Temporal Graphs. ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The parameterized complexity of local search for TSP, more refined
• Fundamentals of parameterized complexity
• Incremental list coloring of graphs, parameterized by conservation
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• Local search: is brute-force avoidable?
• Stable assignment with couples: parameterized complexity and local search
• Correlation clustering
• Average parameterization and partial kernelization for computing medians
• Theoretical aspects of local search.
• Searching the \(k\)-change neighborhood for TSP is W[1-hard]
• On the approximation of correlation clustering and consensus clustering
• NP-hard problems in hierarchical-tree clustering
• Consensus clustering: A resampling-based method for class discovery and visualization of gene expression microarray data
• Cluster graph modification problems
• Parametrized complexity theory.
• Advances in K-means Clustering
• On the hardness of losing weight
• On Local Search and Placement of Meters in Networks
• 10.1162/153244303321897735
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems

This page was built for publication: On the parameterized complexity of consensus clustering