A golden ratio parameterized algorithm for cluster editing

DOI10.1016/J.JDA.2012.04.005MaRDI QIDQ1932356zbMATH OpenOpenAlexFDO

Authors 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 complexityFPTparameterized algorithmcluster editingsearch tree algorithm

Mathematics Subject Classification ID

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

Recommendations

• A golden ratio parameterized algorithm for cluster editing
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Going weighted: parameterized algorithms for cluster editing
• Alternative parameterizations for cluster editing
• A more effective linear kernelization for cluster editing

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 general method to speed up fixed-parameter-tractable algorithms
• A more effective linear kernelization for cluster editing
• A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing
• A new approach to the maximum-flow problem
• Alternative parameterizations for cluster editing
• Automated generation of search tree algorithms for hard graphs modification problems
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Cluster editing: kernelization based on edge cuts
• Even faster parameterized cluster deletion and cluster editing
• Exact algorithms for cluster editing: Evaluation and experiments
• Fixed-parameter algorithms for cluster vertex deletion
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Going weighted: parameterized algorithms for cluster editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• NP-hard problems in hierarchical-tree clustering
• The Complexity of Multiterminal Cuts

Cited in

(27)

• A fast branching algorithm for cluster vertex deletion
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• Cluster editing with locally bounded modifications
• On the complexity of multi-parameterized cluster editing
• Parameterized algorithms for min-max 2-cluster editing
• Even better fixed-parameter algorithms for bicluster editing
• Parameterized algorithms for cluster vertex deletion on degree-4 graphs and general graphs
• On the parameterized complexity of s-club cluster deletion problems
• On the parameterized complexity of \(s\)-club cluster deletion problems
• A new temporal interpretation of cluster editing
• Polyhedral properties of the induced cluster subgraphs
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster editing
• A survey of parameterized algorithms and the complexity of edge modification
• A golden ratio parameterized algorithm for cluster editing
• \((1,1)\)-cluster editing is polynomial-time solvable
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Cograph editing: complexity and parameterized algorithms
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Cluster editing for multi-layer and temporal graphs
• A new temporal interpretation of cluster editing
• Sufficient conditions for edit-optimal clusters
• Improved kernelization and fixed-parameter algorithms for bicluster editing
• A faster algorithm for the cluster editing problem on proper interval graphs
• Shrinkage points of golden rectangle, Fibonacci spirals, and golden spirals
• The graph motif problem parameterized by the structure of the input graph
• (Sub)linear kernels for edge modification problems toward structured graph classes

This page was built for publication: A golden ratio parameterized algorithm for cluster editing

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