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

DOI10.1016/J.JCSS.2020.05.008MaRDI QIDQ2186825zbMATH OpenOpenAlexFDO

Authors Neeldhara Misra, Fahad Panolan, Saket Saurabh

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

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

Recommendations

• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• Cluster deletion revisited
• On Editing Graphs into 2-Club Clusters
• Faster parameterized algorithm for cluster vertex deletion
• Even faster parameterized cluster deletion and cluster editing

Cites work

• A graph‐theoretic definition of a sociometric clique†
• A more relaxed model for graph-based data clustering: s-plex cluster editing
• Aggregating inconsistent information: ranking and clustering
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Clustering with qualitative information
• Correlation clustering
• Fast biclustering by dual parameterization
• On Editing Graphs into 2-Club Clusters
• Parameterized algorithmics and computational experiments for finding 2-clubs
• Parameterized algorithms
• Parameterized computational complexity of finding small-diameter subgraphs
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Which problems have strongly exponential complexity?

Cited in

(10)

• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• 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
• Cluster editing with overlapping communities
• On the parameterized complexity of s-club cluster edge deletion

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

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