On the parameterized complexity of consensus clustering

DOI10.1016/J.TCS.2014.05.002zbMATH Open1360.68506OpenAlexW2029303541MaRDI QIDQ2015135FDOQ2015135

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

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

Recommendations

• On the parameterized complexity of consensus clustering
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• On constructing an optimal consensus clustering from multiple clusterings
• Algorithms and Computation
• On the approximation of correlation clustering and consensus clustering

zbMATH Keywords

local searchNP-hard problemdata clusteringsearch tree algorithm

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• A note on clustering aggregation for binary clusterings
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Title not available (Why is that?)
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• A Biclustering Framework for Consensus Problems
• On the convergence of puck clustering systems
• Parameterized \(k\)-clustering: tractability island
• Clustering and isolation in the consensus problem for partitions
• Title not available (Why is that?)
• On the parameterized complexity of consensus clustering
• Cluster editing for multi-layer and temporal graphs
• On constructing an optimal consensus clustering from multiple clusterings
• Cluster Editing in Multi-Layer and Temporal Graphs.

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

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