Cluster editing with locally bounded modifications

DOI10.1016/j.dam.2012.05.019zbMath1252.05178MaRDI 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

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

Cites Work