Graph-based data clustering with overlaps

DOI10.1016/j.disopt.2010.09.006zbMath1248.90070OpenAlexW1998839458WikidataQ57359689 ScholiaQ57359689MaRDI QIDQ456688

Johannes Uhlmann, Rolf Niedermeier, Michael R. Fellows, Christian Komusiewicz, Jiong Guo

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.09.006

zbMATH Keywords

NP-hardnessfixed-parameter tractabilitykernelization\(W[1\)-hardness]cluster graph modification problemsforbidden subgraph characterization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (27)

Kernel-based methods to identify overlapping clusters with linear and nonlinear boundaries ⋮ Parameterizing edge modification problems above lower bounds ⋮ Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems ⋮ A mathematical programming approach to overlapping community detection ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ Model selection strategies for determining the optimal number of overlapping clusters in additive overlapping partitional clustering ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ A cubic-vertex kernel for flip consensus tree ⋮ 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 ⋮ Explicit linear kernels for packing problems ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Complete mixed integer linear programming formulations for modularity density based clustering ⋮ A new approximate cluster deletion algorithm for diamond-free graphs ⋮ Strong cliques in diamond-free graphs ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph clustering
• Correlation clustering
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter enumerability of cluster editing and related 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
• The maximum edge biclique problem is NP-complete
• NP-hard approximation problems in overlapping clustering.
• Cluster graph modification problems
• Applying modular decomposition to parameterized cluster editing problems
• Parametrized complexity theory.
• Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs
• The Cluster Editing Problem: Implementations and Experiments
• A 2k Kernel for the Cluster Editing Problem
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing
• Editing Graphs into Disjoint Unions of Dense Clusters
• Kernelization: New Upper and Lower Bound Techniques
• Algorithm Theory - SWAT 2004
• Efficient Parameterized Preprocessing for Cluster Editing

This page was built for publication: Graph-based data clustering with overlaps