Even faster parameterized cluster deletion and cluster editing

DOI10.1016/j.ipl.2011.05.003zbMath1260.05156OpenAlexW2052073858MaRDI QIDQ1944120

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 algorithmscluster editingparameterized complexitygraph transformationcluster deletionedge deletioneddge editing

Mathematics Subject Classification ID

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

Related Items (18)

Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ Cluster Editing ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ The cluster deletion problem for cographs ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ On making directed graphs transitive ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions ⋮ Cluster deletion revisited ⋮ Complexity of the cluster deletion problem on subclasses of chordal graphs ⋮ Branch-and-cut approaches for \(p\)-cluster editing ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ Branch-and-price for \(p\)-cluster editing ⋮ Cluster editing with locally bounded modifications ⋮ On the relation of strong triadic closure and cluster deletion ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter enumerability of cluster editing and related problems
• Fixed-parameter algorithms for cluster vertex deletion
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• Cluster editing problem for points on the real line: a polynomial time algorithm
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Beyond the flow decomposition barrier
• The Cluster Editing Problem: Implementations and Experiments
• A 2k Kernel for the Cluster Editing Problem
• Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms

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