On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering

DOI10.7155/jgaa.00570zbMath1489.05145arXiv2006.14972OpenAlexW3205863632MaRDI QIDQ5084692

Aleksander Figiel, Rolf Niedermeier, Anne-Sophie Himmel, André Nichterlein

Publication date: 28 June 2022

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.14972

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

\(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs

Uses Software

• solverALL

Cites Work

• A fast branching algorithm for cluster vertex deletion
• Fundamentals of parameterized complexity
• Graph-based data clustering with overlaps
• Exact algorithms for cluster editing: Evaluation and experiments
• Correlation clustering
• Cluster editing with locally bounded modifications
• Graph-modeled data clustering: Exact algorithms for clique generation
• Combining clickstream analyses and graph-modeled data clustering for identifying common response processes
• Fixed-parameter algorithms for cluster vertex deletion
• Going weighted: parameterized algorithms for cluster editing
• On biconnected and fragile subgraphs of low diameter
• Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
• Parameterized computational complexity of finding small-diameter subgraphs
• Cluster graph modification problems
• Faster parameterized algorithm for cluster vertex deletion
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• On structural parameterizations for the 2-club problem
• On the tractability of finding disjoint clubs in a network
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• The parametric complexity of graph diameter augmentation
• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Hardness of r-dominating set on Graphs of Diameter (r + 1)
• On Editing Graphs into 2-Club Clusters
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• The complexity of finding maximum disjoint paths with length constraints
• Kernelization Lower Bounds by Cross-Composition
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Cluster Editing
• Covering a Graph with Clubs
• On the tractability of covering a graph with 2-clubs

This page was built for publication: On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering