A golden ratio parameterized algorithm for cluster editing

DOI10.1016/j.jda.2012.04.005zbMath1257.05164OpenAlexW2175156123MaRDI QIDQ1932356

Sebastian Böcker

Publication date: 18 January 2013

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.04.005

zbMATH Keywords

computational complexitycluster editingFPTparameterized algorithmsearch tree algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Parameterizing edge modification problems above lower bounds ⋮ A new temporal interpretation of cluster editing ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Cluster Editing ⋮ On the complexity of multi-parameterized cluster editing ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ 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 ⋮ Sufficient conditions for edit-optimal clusters ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ Cluster editing with locally bounded modifications ⋮ Even better fixed-parameter algorithms for bicluster editing ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Shrinkage points of golden rectangle, Fibonacci spirals, and golden spirals ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ A fast branching algorithm for cluster vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• A \(2k\) kernel for the cluster editing problem
• Exact algorithms for cluster editing: Evaluation and experiments
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter algorithms for cluster vertex deletion
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• NP-hard problems in hierarchical-tree clustering
• A general method to speed up fixed-parameter-tractable algorithms
• Cluster editing: kernelization based on edge cuts
• Automated generation of search tree algorithms for hard graphs modification problems
• Even faster parameterized cluster deletion and cluster editing
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• Alternative Parameterizations for Cluster Editing
• Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms
• A new approach to the maximum-flow problem
• The Complexity of Multiterminal Cuts
• Fixed-parameter tractability of multicut parameterized by the size of the cutset