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

DOI10.1137/090767285MaRDI QIDQ3013154zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(23)

• Multivariate algorithmics for finding cohesive subnetworks
• Combining clickstream analyses and graph-modeled data clustering for identifying common response processes
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Optimization problems for the maximum \(k\)-plex
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• 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
• Alternative parameterizations for cluster editing
• A survey of parameterized algorithms and the complexity of edge modification
• \( \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

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)