A more effective linear kernelization for cluster editing
From MaRDI portal
Publication:1006044
DOI10.1016/J.TCS.2008.10.021zbMATH Open1162.68025OpenAlexW2174049388MaRDI QIDQ1006044FDOQ1006044
Authors: Jiong Guo 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Clustering with qualitative information
- Correlation clustering
- Parametrized complexity theory.
- Title not available (Why is that?)
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Title not available (Why is that?)
- Applying Modular Decomposition to Parameterized Bicluster Editing
- Aggregating inconsistent information
- Cluster graph modification problems
- Error compensation in leaf power problems
- A More Effective Linear Kernelization for Cluster Editing
- Graph-Theoretic Concepts in Computer Science
- Going weighted: parameterized algorithms for cluster editing
- NP-hard problems in hierarchical-tree clustering
- The Cluster Editing Problem: Implementations and Experiments
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Title not available (Why is that?)
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Graph-modeled data clustering: Exact algorithms for clique generation
- Going Weighted: Parameterized Algorithms for Cluster Editing
- Correlation clustering with a fixed number of clusters
- Exact Algorithms for Cluster Editing: Evaluation and Experiments
Cited In (56)
- Fast FPT-Algorithms for Cleaning Grids
- A \(2k\) kernel for the cluster editing problem
- Cluster editing with locally bounded modifications revisited
- Efficient algorithms for cluster editing
- Cluster editing: kernelization based on edge cuts
- Kernelization: new upper and lower bound techniques
- A \(2k\) kernel for the cluster editing problem
- On subgraph complementation to \(H\)-free graphs
- Cluster editing: kernelization based on edge cuts
- On structural parameterizations of load coloring
- On Making Directed Graphs Transitive
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Cluster editing with locally bounded modifications
- Graph-Based Data Clustering with Overlaps
- On the complexity of multi-parameterized cluster editing
- On making directed graphs transitive
- Graph-based data clustering with overlaps
- Efficient Parameterized Preprocessing for Cluster Editing
- Parameterized algorithms for min-max 2-cluster editing
- Exact algorithms for cluster editing: Evaluation and experiments
- An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
- Editing graphs into disjoint unions of dense clusters
- Destroying Bicolored $P_3$s by Deleting Few Edges
- Two edge modification problems without polynomial kernels
- A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
- A simple and improved parameterized algorithm for bicluster editing
- Going weighted: parameterized algorithms for cluster editing
- The Multi-parameterized Cluster Editing Problem
- Even faster parameterized cluster deletion and cluster editing
- A More Effective Linear Kernelization for Cluster Editing
- Cluster editing
- A golden ratio parameterized algorithm for cluster editing
- Parameterized dynamic cluster editing
- A survey of parameterized algorithms and the complexity of edge modification
- Alternative parameterizations for cluster editing
- \((1,1)\)-cluster editing is polynomial-time solvable
- Two edge modification problems without polynomial kernels
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Fixed-parameter enumerability of cluster editing and related problems
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- Kernelization of packing problems
- A new approximate cluster deletion algorithm for diamond-free graphs
- Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
- A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing
- An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem
- Editing graphs into few cliques: complexity, approximation, and kernelization schemes
- Kernels for packing and covering problems
- Confluence in data reduction: bridging graph transformation and kernelization
- On subgraph complementation to \(H\)-free Graphs
- Iterative compression and exact algorithms
- Cluster editing problem for points on the real line: a polynomial time algorithm
- Dominator coloring and CD coloring in almost cluster graphs
- On structural parameterizations of load coloring
- A quasi-quadratic vertex-kernel for cograph edge editing
- (Sub)linear kernels for edge modification problems towards structured graph classes
This page was built for publication: A more effective linear kernelization for cluster editing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1006044)
