Editing graphs into disjoint unions of dense clusters

DOI10.1007/S00453-011-9487-4MaRDI QIDQ652530zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Iyad Kanj, Christian Komusiewicz, Johannes Uhlmann

Publication date 14 December 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9487-4

zbMATH Keywords

data reductionNP-hardnessparameterized complexityclique relaxationscluster editingforbidden subgraph characterization

Mathematics Subject Classification ID

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

Recommendations

• Editing graphs into disjoint unions of dense clusters
• Complexity of dense bicluster editing problems
• Alternative parameterizations for cluster editing
• Cluster editing with locally bounded modifications
• Cluster graph modification problems

Cites work

• scientific article; zbMATH DE number 2086259 (Why is no real title available?)
• scientific article; zbMATH DE number 3487498 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A \(2k\) kernel for the cluster editing problem
• A graph‐theoretic generalization of the clique concept
• A more effective linear kernelization for cluster editing
• A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Correlation clustering
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Efficient Parameterized Preprocessing for Cluster Editing
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Going weighted: parameterized algorithms for cluster editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• NP-hard problems in hierarchical-tree clustering
• Network Analysis
• On the parameterized complexity of multiple-interval graph problems
• THE MAXIMUM CONNECTIVITY OF A GRAPH
• The Cluster Editing Problem: Implementations and Experiments

Cited in

(13)

• Multivariate algorithmics for finding cohesive subnetworks
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Complexity of dense bicluster editing problems
• Edge-editing to a dense and a sparse graph class
• Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
• On Editing Graphs into 2-Club Clusters
• Cluster editing with vertex splitting
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Editing graphs into disjoint unions of dense clusters
• Sufficient conditions for edit-optimal clusters
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

This page was built for publication: Editing graphs into disjoint unions of dense clusters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652530)