Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?

DOI10.1016/j.jcss.2020.05.008zbMath1445.68171OpenAlexW3028824564MaRDI QIDQ2186825

Saket Saurabh, Fahad Panolan, Neeldhara Misra

Publication date: 9 June 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2020.05.008

zbMATH Keywords

\(s\)-clubscluster edge deletionETH-hardnessparameterized subexponential time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (7)

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On the parameterized complexity of s-club cluster deletion problems ⋮ On the parameterized complexity of \(s\)-club cluster deletion problems ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering

Cites Work

• Correlation clustering
• Cluster editing with locally bounded modifications
• Which problems have strongly exponential complexity?
• Parameterized computational complexity of finding small-diameter subgraphs
• Cluster graph modification problems
• On structural parameterizations for the 2-club problem
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Clustering with qualitative information
• Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?
• On Editing Graphs into 2-Club Clusters
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• A graph‐theoretic definition of a sociometric clique†
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Fast biclustering by dual parameterization
• Parameterized Algorithms
• Aggregating inconsistent information

This page was built for publication: Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?