A more effective linear kernelization for cluster editing
From MaRDI portal
Publication:1006044
DOI10.1016/j.tcs.2008.10.021zbMath1162.68025OpenAlexW2174049388MaRDI QIDQ1006044
Publication date: 17 March 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.021
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational methods for problems pertaining to biology (92-08)
Related Items (47)
Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ On structural parameterizations of load coloring ⋮ Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes ⋮ Parameterizing edge modification problems above lower bounds ⋮ On Making Directed Graphs Transitive ⋮ Two edge modification problems without polynomial kernels ⋮ Graph-Based Data Clustering with Overlaps ⋮ Cluster Editing ⋮ On the complexity of multi-parameterized cluster editing ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ On subgraph complementation to \(H\)-free graphs ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ A \(2k\) kernel for the cluster editing problem ⋮ On making directed graphs transitive ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Even faster parameterized cluster deletion and cluster editing ⋮ Graph-based data clustering with overlaps ⋮ Editing graphs into disjoint unions of dense clusters ⋮ Parameterized dynamic cluster editing ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions ⋮ On structural parameterizations of load coloring ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ Cluster editing: kernelization based on edge cuts ⋮ Exact algorithms for cluster editing: Evaluation and experiments ⋮ Iterative compression and exact algorithms ⋮ Cluster editing with locally bounded modifications ⋮ Kernels for packing and covering problems ⋮ On the relation of strong triadic closure and cluster deletion ⋮ Cluster Editing: Kernelization Based on Edge Cuts ⋮ Efficient algorithms for cluster editing ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ A new approximate cluster deletion algorithm for diamond-free graphs ⋮ Alternative Parameterizations for Cluster Editing ⋮ A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing ⋮ A simple and improved parameterized algorithm for bicluster editing ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ Going weighted: parameterized algorithms for cluster editing ⋮ On subgraph complementation to \(H\)-free Graphs ⋮ Unnamed Item ⋮ The Multi-parameterized Cluster Editing Problem ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Correlation clustering
- Graph-modeled data clustering: Exact algorithms for clique generation
- Going weighted: parameterized algorithms for cluster editing
- NP-hard problems in hierarchical-tree clustering
- Cluster graph modification problems
- Parametrized complexity theory.
- Error compensation in leaf power problems
- Clustering with qualitative information
- Applying Modular Decomposition to Parameterized Bicluster Editing
- The Cluster Editing Problem: Implementations and Experiments
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Exact Algorithms for Cluster Editing: Evaluation and Experiments
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Correlation clustering with a fixed number of clusters
- Polynomial-time data reduction for dominating set
- A More Effective Linear Kernelization for Cluster Editing
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Going Weighted: Parameterized Algorithms for Cluster Editing
- Graph-Theoretic Concepts in Computer Science
- Aggregating inconsistent information
This page was built for publication: A more effective linear kernelization for cluster editing
