Tight bounds for parameterized complexity of cluster editing with a small number of clusters

DOI10.1016/j.jcss.2014.04.015zbMath1311.68076OpenAlexW1985427743WikidataQ60488409 ScholiaQ60488409MaRDI QIDQ2453563

Yngve Villanger, Michał Pilipczuk, Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk

Publication date: 10 June 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.04.015

zbMATH Keywords

cluster editingparameterized complexitycorrelation clusteringsubexponential-time algorithmsexponential-time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (31)

A parameterized complexity view on collapsing \(k\)-cores ⋮ Paths to Trees and Cacti ⋮ Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes ⋮ Reducing rank of the adjacency matrix by graph modification ⋮ Reducing Rank of the Adjacency Matrix by Graph Modification ⋮ A new temporal interpretation of cluster editing ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule? ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On the parameterized complexity of s-club cluster deletion problems ⋮ On the parameterized complexity of \(s\)-club cluster deletion problems ⋮ Parameterized low-rank binary matrix approximation ⋮ Parameterized dynamic cluster editing ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Branch-and-cut approaches for \(p\)-cluster editing ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ Paths to trees and cacti ⋮ Unnamed Item ⋮ Branch-and-price for \(p\)-cluster editing ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ A polynomial kernel for trivially perfect editing ⋮ Cluster Editing in Multi-Layer and Temporal Graphs. ⋮ Parameterized Dynamic Cluster Editing ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ A fast branching algorithm for cluster vertex deletion

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 algorithms for cluster editing: Evaluation and experiments
• Exact exponential algorithms.
• Editing graphs into disjoint unions of dense clusters
• Correlation clustering
• Cluster editing with locally bounded modifications
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter enumerability of cluster editing and related problems
• A more effective linear kernelization for cluster editing
• Which problems have strongly exponential complexity?
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• A golden ratio parameterized algorithm for cluster editing
• Even faster parameterized cluster deletion and cluster editing
• Clustering with partial information
• Applying modular decomposition to parameterized cluster editing problems
• Parametrized complexity theory.
• Clustering with qualitative information
• What’s Next? Future Directions in Parameterized Complexity
• Tight bounds for parameterized complexity of Cluster Editing
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• Cluster Editing: Kernelization Based on Edge Cuts
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Correlation clustering with a fixed number of clusters
• Fast FAST
• Cluster Editing
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Aggregating inconsistent information
• Quadratic forms on graphs

This page was built for publication: Tight bounds for parameterized complexity of cluster editing with a small number of clusters