Cluster graph modification problems

DOI10.1016/j.dam.2004.01.007zbMath1068.68107OpenAlexW2107223449MaRDI QIDQ1885821

Ron Shamir, Roded Sharan, Dekel Tsur

Publication date: 12 November 2004

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

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

zbMATH Keywords

Clustering Complexity Approximation Cluster graph Graph modification problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion, $s$-club cluster vertex deletion on interval and well-partitioned chordal graphs, $(1,1)$-cluster editing is polynomial-time solvable, Structural parameterization of cluster deletion, Digital topological groups, Splitting plane graphs to outerplanarity, $s$-club cluster vertex deletion on interval and well-partitioned chordal graphs, K‐Plus anticlustering: An improved k‐means criterion for maximizing between‐group similarity, Algorithms for 2-club cluster deletion problems using automated generation of branching rules, Bounds for the clustering complexity in a graph clustering problem with clusters of bounded size, 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 combinatorial multi-armed bandit approach to correlation clustering, Unnamed Item, Unnamed Item, On the effectiveness of the incremental approach to minimal chordal edge modification, Combining clickstream analyses and graph-modeled data clustering for identifying common response processes, Destroying Bicolored $P_3$s by Deleting Few Edges, Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes, Parameterizing edge modification problems above lower bounds, On the polytope faces of the graph approximation problem, Reducing rank of the adjacency matrix by graph modification, Reducing Rank of the Adjacency Matrix by Graph Modification, Graph-Based Data Clustering with Overlaps, 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, Polynomial kernels for 3-leaf power graph modification problems, On the complexity of multi-parameterized cluster editing, Cluster editing problem for points on the real line: a polynomial time algorithm, $2$-Approximation algorithms for two graph clustering problems, Parameterized algorithms for min-max 2-cluster editing, On polynomial kernelization of $\mathcal H$-\textsc{free edge deletion}, Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds, Polynomial kernels for proper interval completion and related problems, The cluster deletion problem for cographs, Subexponential algorithm for $d$-cluster edge deletion: exception or rule?, New heuristics for the bicluster editing problem, Improved Algorithms for Bicluster Editing, Exact Algorithms for Cluster Editing: Evaluation and Experiments, A $2k$ kernel for the cluster editing problem, On making directed graphs transitive, Graph clustering with a constraint on cluster sizes, Exact-2-relation graphs, Even faster parameterized cluster deletion and cluster editing, Approximation and tidying -- a problem kernel for $s$-plex cluster vertex deletion, Sufficient conditions for edit-optimal clusters, On 2-clubs in graph-based data clustering: theory and algorithm engineering, On the (non-)existence of polynomial kernels for $P _{l }$-free edge modification problems, Hardness of subgraph and supergraph problems in $c$-tournaments, Graph-based data clustering with overlaps, Graph clustering, Editing graphs into disjoint unions of dense clusters, The community structure of human cellular signaling network, Approximation algorithms for bounded degree phylogenetic roots, Parameterized dynamic cluster editing, Finding the closest ultrametric, 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, On a semi-superwized graph clustering problem, APPROXIMATE ALGORITHMS FOR GRAPH CLUSTERING PROBLEM, ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM, An improved parameterized algorithm for the $p$-cluster vertex deletion problem, Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability, Cluster editing: kernelization based on edge cuts, Exact algorithms for cluster editing: Evaluation and experiments, Fixed-parameter enumerability of cluster editing and related problems, On the parameterized complexity of consensus clustering, Clustering with partial information, Cluster editing with locally bounded modifications, Applying modular decomposition to parameterized cluster editing problems, Polyhedral properties of the induced cluster subgraphs, Clustering with Partial Information, Fixed-parameter algorithms for cluster vertex deletion, On the relation of strong triadic closure and cluster deletion, Strong triadic closure in cographs and graphs of low maximum degree, Unnamed Item, Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs, Cluster Editing: Kernelization Based on Edge Cuts, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, Parameterized algorithms for module map problems, Parameterized Enumeration for Modification Problems, Efficient algorithms for cluster editing, Correlation clustering in data streams, Cluster deletion on interval graphs and split related graphs, Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs, Indirect identification of horizontal gene transfer, Closest 4-leaf power is fixed-parameter tractable, Fixed-Parameter Algorithms for Cluster Vertex Deletion, A new approximate cluster deletion algorithm for diamond-free graphs, A more effective linear kernelization for cluster editing, Alternative Parameterizations for Cluster Editing, An Approximation Algorithm for a Semi-supervised Graph Clustering Problem, A parallel hybrid metaheuristic for bicluster editing, Online clique clustering, On the threshold of intractability, The Branch and Cut Method for the Clique Partitioning Problem, Polynomial Kernels for Proper Interval Completion and Related Problems, A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing, Graph Clustering in All Parameter Regimes, Parameterized Dynamic Cluster Editing, Hardness of edge-modification problems, Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms, Going weighted: parameterized algorithms for cluster editing, A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis, Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: a review, THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS, Going Weighted: Parameterized Algorithms for Cluster Editing, 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, The generic complexity of the bounded problem of graphs clustering

Cites Work