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

cluster editingcomputational complexityFPTparameterized algorithmsearch tree algorithm

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• NP-hard problems in hierarchical-tree clustering
• The Complexity of Multiterminal Cuts

Cited in

(42)

• Going weighted: parameterized algorithms for cluster editing
• Automated generation of search tree algorithms for hard graphs modification problems
• Even better fixed-parameter algorithms for bicluster editing
• Polyhedral properties of the induced cluster subgraphs
• (Sub)linear kernels for edge modification problems toward structured graph classes
• A new temporal interpretation of cluster editing
• Shrinkage points of golden rectangle, Fibonacci spirals, and golden spirals
• The graph motif problem parameterized by the structure of the input graph
• On the complexity of multi-parameterized cluster editing
• Parameterized algorithms for min-max 2-cluster editing
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• A fast branching algorithm for cluster vertex deletion
• Cograph editing: complexity and parameterized algorithms
• A golden ratio parameterized algorithm for cluster editing
• A faster algorithm for the cluster editing problem on proper interval graphs
• Cluster editing
• Going Weighted: Parameterized Algorithms for 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
• A new temporal interpretation of cluster editing
• Parameterized algorithms for cluster vertex deletion on degree-4 graphs and general graphs
• Cluster editing for multi-layer and temporal graphs
• Improved kernelization and fixed-parameter algorithms for bicluster editing
• Bicluster editing with overlaps: a vertex splitting approach
• Improved parameterized algorithms for cluster vertex deletion
• Correlation clustering with vertex splitting
• A fixed-parameter branching algorithm for chromatic correlation clustering
• Smaller kernels for 3-leaf power modifications problems
• Graph clustering problems under the Lens of parameterized local search
• Applying a cut-based data reduction rule for weighted cluster editing in polynomial time
• Exact and heuristic solution approaches for the cluster deletion problem on general graphs
• Cluster editing with vertex splitting
• Cluster editing parameterized above modification-disjoint P₃-packings
• The complexity of cluster vertex splitting and company
• Cluster editing with locally bounded modifications
• Cluster editing parameterized above modification-disjoint P₃-Packings
• Graph clustering problems under the Lens of parameterized local search
• Cluster editing on cographs and related classes
• Sufficient conditions for edit-optimal clusters

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)