Editing graphs into disjoint unions of dense clusters

DOI10.1007/s00453-011-9487-4zbMath1230.68091OpenAlexW2034185455MaRDI QIDQ652530

Christian Komusiewicz, Iyad A. Kanj, Johannes Uhlmann, Jiong Guo

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-hardnesscluster editingparameterized complexityclique relaxationsforbidden subgraph characterization

Mathematics Subject Classification ID

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

Related Items (6)

Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• Graph-modeled data clustering: Exact algorithms for clique generation
• On the parameterized complexity of multiple-interval graph problems
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• NP-hard problems in hierarchical-tree clustering
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Cluster graph modification problems
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• Cluster Editing: Kernelization Based on Edge Cuts
• Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
• The Cluster Editing Problem: Implementations and Experiments
• A 2k Kernel for the Cluster Editing Problem
• A graph‐theoretic generalization of the clique concept
• Efficient Parameterized Preprocessing for Cluster Editing
• Network Analysis
• THE MAXIMUM CONNECTIVITY OF A GRAPH

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