Editing graphs into disjoint unions of dense clusters
DOI10.1007/S00453-011-9487-4zbMATH Open1230.68091OpenAlexW2034185455MaRDI QIDQ652530FDOQ652530
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
Recommendations
data reductionNP-hardnessparameterized complexityclique relaxationscluster editingforbidden subgraph characterization
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)
Cites Work
- Title not available (Why is that?)
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Correlation clustering
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A graph‐theoretic generalization of the clique concept
- On the parameterized complexity of multiple-interval graph problems
- THE MAXIMUM CONNECTIVITY OF A GRAPH
- Cluster graph modification problems
- Network Analysis
- A more effective linear kernelization for cluster editing
- A \(2k\) kernel for the cluster editing problem
- Going weighted: parameterized algorithms for cluster editing
- NP-hard problems in hierarchical-tree clustering
- The Cluster Editing Problem: Implementations and Experiments
- Efficient Parameterized Preprocessing for Cluster Editing
- Graph-modeled data clustering: Exact algorithms for clique generation
- Deterministic pivoting algorithms for constrained ranking and clustering problems
- A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing
- Cluster editing: kernelization based on edge cuts
Cited In (13)
- 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
- Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
- Edge-editing to a dense and a sparse graph class
- On Editing Graphs into 2-Club Clusters
- Cluster editing with vertex splitting
- Editing graphs into disjoint unions of dense clusters
- Tight bounds for parameterized complexity of cluster editing with a small number of 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
- Multivariate algorithmics for finding cohesive subnetworks
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)
