Cluster editing with locally bounded modifications

DOI10.1016/j.dam.2012.05.019zbMath1252.05178OpenAlexW2168123742MaRDI QIDQ713321

Johannes Uhlmann, Christian Komusiewicz

Publication date: 26 October 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.05.019

zbMATH Keywords

data reduction graph modification problems parameterized algorithmics exponential-time hypothesis

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (49)

Combining clickstream analyses and graph-modeled data clustering for identifying common response processes ⋮ Parameterizing edge modification problems above lower bounds ⋮ Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ A new temporal interpretation of cluster editing ⋮ Cluster Editing ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ On the complexity of multi-parameterized cluster editing ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ On polynomial kernelization of $\mathcal H$-\textsc{free edge deletion} ⋮ The cluster deletion problem for cographs ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ Subexponential algorithm for $d$-cluster edge deletion: exception or rule? ⋮ An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion ⋮ $(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 ⋮ On the parameterized complexity of s-club cluster deletion problems ⋮ On the parameterized complexity of $s$-club cluster deletion problems ⋮ Sufficient conditions for edit-optimal clusters ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ 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 ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ Complexity of the cluster deletion problem on subclasses of chordal graphs ⋮ Branch-and-cut approaches for $p$-cluster editing ⋮ An improved parameterized algorithm for the $p$-cluster vertex deletion problem ⋮ Branch-and-price for $p$-cluster editing ⋮ Even better fixed-parameter algorithms for bicluster editing ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ On the relation of strong triadic closure and cluster deletion ⋮ Strong triadic closure in cographs and graphs of low maximum degree ⋮ Unnamed Item ⋮ Parameterized algorithms for module map problems ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ A polynomial kernel for trivially perfect editing ⋮ A new approximate cluster deletion algorithm for diamond-free graphs ⋮ Cluster Editing in Multi-Layer and Temporal Graphs. ⋮ Parameterized Dynamic Cluster Editing ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to $P_4$-sparse graphs ⋮ The Multi-parameterized Cluster Editing Problem ⋮ A fast branching algorithm for cluster vertex deletion

Cites Work

This page was built for publication: Cluster editing with locally bounded modifications