A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
From MaRDI portal
Publication:3013154
DOI10.1137/090767285zbMath1221.05293OpenAlexW1988853946MaRDI QIDQ3013154
Christian Komusiewicz, Johannes Uhlmann, Rolf Niedermeier, Jiong Guo
Publication date: 18 July 2011
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090767285
data reductionNP-hard problemsfixed-parameter tractabilityexact algorithmsgraph modification\(k\)-plexforbidden subgraph characterizationdense subgraphs
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Algorithms in computer science (68W99)
Related Items
Combining clickstream analyses and graph-modeled data clustering for identifying common response processes ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule? ⋮ 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 ⋮ Editing graphs into disjoint unions of dense clusters ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Alternative Parameterizations for Cluster Editing ⋮ On the tractability of covering a graph with 2-clubs ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ Optimization problems for the maximum \(k\)-plex
