Going weighted: parameterized algorithms for cluster editing

DOI10.1016/j.tcs.2009.05.006zbMath1178.68373OpenAlexW2133729430MaRDI QIDQ1040589

Q. B. A. Bui, Sebastian Briesemeister, Sebastian Böcker, Anke Truss

Publication date: 25 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.006

zbMATH Keywords

data clusteringfixed-parameter tractabilityexact algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (31)

Multistage graph problems on a global budget ⋮ Parameterizing edge modification problems above lower bounds ⋮ Cluster Editing ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ On the complexity of multi-parameterized cluster editing ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ Structural parameterization of cluster deletion ⋮ A \(2k\) kernel for the cluster editing problem ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Even faster parameterized cluster deletion and cluster editing ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ A PTAS for the Cluster Editing Problem on Planar Graphs ⋮ Graph-based data clustering with overlaps ⋮ Editing graphs into disjoint unions of dense clusters ⋮ Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ Cluster editing: kernelization based on edge cuts ⋮ Unnamed Item ⋮ Clustering with partial information ⋮ Cluster editing with locally bounded modifications ⋮ Cluster Editing: Kernelization Based on Edge Cuts ⋮ Parameterized algorithms for module map problems ⋮ A more effective linear kernelization for cluster editing ⋮ Alternative Parameterizations for Cluster Editing ⋮ A simple and improved parameterized algorithm for bicluster editing ⋮ Going weighted: parameterized algorithms for cluster editing ⋮ The Multi-parameterized Cluster Editing Problem

Cites Work

• Unnamed Item
• Graph-modeled data clustering: Exact algorithms for clique generation
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• NP-hard problems in hierarchical-tree clustering
• A cutting plane algorithm for a clustering problem
• A general method to speed up fixed-parameter-tractable algorithms
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• The Cluster Editing Problem: Implementations and Experiments
• Exact Algorithms for Cluster Editing: Evaluation and Experiments
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems

This page was built for publication: Going weighted: parameterized algorithms for cluster editing