Cluster editing: kernelization based on edge cuts

DOI10.1007/s00453-011-9595-1zbMath1253.68144OpenAlexW2170771113MaRDI QIDQ1759680

Yixin Cao, Jian'er Chen

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9595-1

zbMATH Keywords

bioinformaticscluster editingkernelizationparameterized computationedge-cut

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (26)

Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ A new temporal interpretation of cluster editing ⋮ Cluster Editing ⋮ On the complexity of multi-parameterized cluster editing ⋮ On subgraph complementation to \(H\)-free graphs ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ Structural parameterization of cluster deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Unnamed Item ⋮ Sufficient conditions for edit-optimal clusters ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Parameterized dynamic cluster editing ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ Approximate association via dissociation ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Cluster Editing in Multi-Layer and Temporal Graphs. ⋮ Parameterized Dynamic Cluster Editing ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ A polynomial kernel for diamond-free editing ⋮ On subgraph complementation to \(H\)-free Graphs ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ The Multi-parameterized Cluster Editing Problem

Cites Work

• Kernels for feedback arc set in tournaments
• Correlation clustering
• Average parameterization and partial kernelization for computing medians
• Graph-modeled data clustering: Exact algorithms for clique generation
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• NP-hard problems in hierarchical-tree clustering
• Cluster graph modification problems
• Clustering with qualitative information
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
• A 2k Kernel for the Cluster Editing Problem
• Fast FAST
• A Combinatorial Decomposition Theory
• Efficient Parameterized Preprocessing for Cluster Editing

This page was built for publication: Cluster editing: kernelization based on edge cuts