Even faster parameterized cluster deletion and cluster editing

DOI10.1016/J.IPL.2011.05.003MaRDI QIDQ1944120zbMATH OpenOpenAlexFDO

Authors Sebastian Böcker, Peter Damaschke

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.05.003

zbMATH Keywords

graph algorithmsparameterized complexitygraph transformationcluster deletioncluster editingedge deletioneddge editing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Alternative parameterizations for cluster editing
• Cluster deletion revisited
• scientific article; zbMATH DE number 2011849
• Graph-modeled data clustering: Exact algorithms for clique generation
• Cluster editing with locally bounded modifications

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A \(2k\) kernel for the cluster editing problem
• A more effective linear kernelization for cluster editing
• Automated generation of search tree algorithms for hard graphs modification problems
• Beyond the flow decomposition barrier
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Cluster editing problem for points on the real line: a polynomial time algorithm
• Cluster graph modification problems
• Fixed-parameter algorithms for cluster vertex deletion
• Fixed-parameter enumerability of cluster editing and related problems
• Going weighted: parameterized algorithms for cluster editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• The Cluster Editing Problem: Implementations and Experiments

Cited in

(21)

• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• Cluster deletion revisited
• Parameterized Dynamic Cluster Editing
• Cluster editing
• Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
• The cluster deletion problem for cographs
• Faster parameterized algorithm for cluster vertex deletion
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• On making directed graphs transitive
• A survey of parameterized algorithms and the complexity of edge modification
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• The maximum independent union of cliques problem: complexity and exact approaches
• Destroying Bicolored $P_3$s by Deleting Few Edges
• Bounded-degree techniques accelerate some parameterized graph algorithms
• A golden ratio parameterized algorithm for cluster editing
• Branch-and-cut approaches for \(p\)-cluster editing
• An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem
• Cluster editing with locally bounded modifications
• Branch-and-price for \(p\)-cluster editing

This page was built for publication: Even faster parameterized cluster deletion and cluster editing

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