Tight bounds for parameterized complexity of cluster editing with a small number of clusters
From MaRDI portal
Publication:2453563
DOI10.1016/J.JCSS.2014.04.015zbMATH Open1311.68076OpenAlexW1985427743WikidataQ60488409 ScholiaQ60488409MaRDI QIDQ2453563FDOQ2453563
Authors: Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Yngve Villanger 
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
Recommendations
parameterized complexitycorrelation clusteringcluster editingsubexponential-time algorithmsexponential-time hypothesis
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- A golden ratio parameterized algorithm for cluster editing
- Applying modular decomposition to parameterized cluster editing problems
- Clustering with qualitative information
- A \(2k\) kernel for the cluster editing problem
- Cluster editing
- Aggregating inconsistent information: ranking and clustering
- Exact exponential algorithms.
- Correlation clustering
- Cluster editing with locally bounded modifications
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Lower bounds based on the exponential time hypothesis
- Graph-based data clustering with overlaps
- Editing graphs into disjoint unions of dense clusters
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Title not available (Why is that?)
- Bidimensionality: new connections between FPT algorithms and PTASs
- Title not available (Why is that?)
- Fast FAST
- Cluster graph modification problems
- Subexponential parameterized algorithm for minimum fill-in
- Quadratic forms on graphs (extended abstract)
- A more effective linear kernelization for cluster editing
- Even faster parameterized cluster deletion and cluster editing
- Exact algorithms for cluster editing: Evaluation and experiments
- Graph-modeled data clustering: Exact algorithms for clique generation
- Fixed-parameter enumerability of cluster editing and related problems
- Going Weighted: Parameterized Algorithms for Cluster Editing
- Tight bounds for parameterized complexity of Cluster Editing
- Cluster editing: kernelization based on edge cuts
- Correlation clustering with a fixed number of clusters
- A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing
- Cluster editing: kernelization based on edge cuts
- What's next? Future directions in parameterized complexity
- Clustering with partial information
Cited In (38)
- A parameterized complexity view on collapsing \(k\)-cores
- A fast branching algorithm for cluster vertex deletion
- Dominator coloring and CD coloring in almost cluster graphs
- Paths to trees and cacti
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Parameterized algorithms for min-max 2-cluster editing
- Parameterized Dynamic Cluster Editing
- Reducing rank of the adjacency matrix by graph modification
- Branch-and-price for \(p\)-cluster editing
- Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
- 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
- A new temporal interpretation of cluster editing
- Tight bounds for parameterized complexity of Cluster Editing
- Rank reduction of oriented graphs by vertex and edge deletions
- The Multi-parameterized Cluster Editing Problem
- Polyhedral properties of the induced cluster subgraphs
- Parameterized low-rank binary matrix approximation
- Title not available (Why is that?)
- Parameterized dynamic cluster editing
- A survey of parameterized algorithms and the complexity of edge modification
- Graph-Theoretic Concepts in Computer Science
- On width measures and topological problems on semi-complete digraphs
- A polynomial kernel for trivially perfect editing
- A PTAS for the Cluster Editing Problem on Planar Graphs
- Cluster editing for multi-layer and temporal graphs
- A new temporal interpretation of cluster editing
- Reducing rank of the adjacency matrix by graph modification
- Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
- Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
- Exploring the subexponential complexity of completion problems
- Branch-and-cut approaches for \(p\)-cluster editing
- An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem
- Editing graphs into few cliques: complexity, approximation, and kernelization schemes
- Cluster Editing in Multi-Layer and Temporal Graphs.
- Paths to Trees and Cacti
- (Sub)linear kernels for edge modification problems toward structured graph classes
This page was built for publication: Tight bounds for parameterized complexity of cluster editing with a small number of clusters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453563)
