A more relaxed model for graph-based data clustering: s-plex cluster editing

DOI10.1137/090767285zbMATH Open1221.05293OpenAlexW1988853946MaRDI QIDQ3013154FDOQ3013154

Authors: Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann 

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

Recommendations

• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• Kernelization through Tidying
• Graph-modeled data clustering: Exact algorithms for clique generation
• Generalized graph clustering: recognizing \((p,q)\)-cluster graphs

zbMATH Keywords

data reductionexact algorithmsfixed-parameter tractabilityNP-hard problemsgraph modification\(k\)-plexforbidden subgraph characterizationdense subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Cited In (23)

• Combining clickstream analyses and graph-modeled data clustering for identifying common response processes
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• Optimization problems for the maximum \(k\)-plex
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• A generalization of Nemhauser and Trotter's local optimization theorem
• Editing graphs into disjoint unions of dense clusters
• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
• Polyhedral properties of the induced cluster subgraphs
• A cubic-vertex kernel for flip consensus tree
• A golden ratio parameterized algorithm for cluster editing
• A survey of parameterized algorithms and the complexity of edge modification
• Alternative parameterizations for cluster editing
• \( \gamma \)-clustering problems: classical and parametrized complexity
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Generalized graph clustering: recognizing \((p,q)\)-cluster graphs
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing
• On the tractability of covering a graph with 2-clubs
• Multivariate algorithmics for finding cohesive subnetworks

This page was built for publication: A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing

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