A more effective linear kernelization for cluster editing
From MaRDI portal
Publication:1006044
DOI10.1016/j.tcs.2008.10.021zbMath1162.68025MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
92-08: Computational methods for problems pertaining to biology
Related Items
Graph-Based Data Clustering with Overlaps, Cluster Editing, Unnamed Item, On the relation of strong triadic closure and cluster deletion, Efficient algorithms for cluster editing, Your rugby mates don't need to know your colleagues: triadic closure with edge colors, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, A \(2k\) kernel for the cluster editing problem, On making directed graphs transitive, Graph-based data clustering with overlaps, Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions, An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem, Exact algorithms for cluster editing: Evaluation and experiments, Editing graphs into disjoint unions of dense clusters, Cluster editing with locally bounded modifications, On structural parameterizations of load coloring, Going weighted: parameterized algorithms for cluster editing, Parameterizing edge modification problems above lower bounds, Two edge modification problems without polynomial kernels, Cluster editing: kernelization based on edge cuts, A golden ratio parameterized algorithm for cluster editing, Even faster parameterized cluster deletion and cluster editing, A simple and improved parameterized algorithm for bicluster editing, Parameterized dynamic cluster editing, Iterative compression and exact algorithms, Kernels for packing and covering problems, A new approximate cluster deletion algorithm for diamond-free graphs, A linear-time kernelization for the rooted \(k\)-leaf outbranching problem, On the complexity of multi-parameterized cluster editing, Parameterized algorithms for min-max 2-cluster editing, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, The Multi-parameterized Cluster Editing Problem, Cluster Editing: Kernelization Based on Edge Cuts, Alternative Parameterizations for Cluster Editing, On Making Directed Graphs Transitive, Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes, A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing, Kernelization: New Upper and Lower Bound Techniques, Two Edge Modification Problems without Polynomial Kernels
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
