Exact algorithms for cluster editing: Evaluation and experiments

DOI10.1007/S00453-009-9339-7zbMath1215.68169OpenAlexW2137745608MaRDI QIDQ534775

Gunnar W. Klau, Sebastian Briesemeister, Sebastian Böcker

Publication date: 10 May 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/14843

zbMATH Keywords

branch-and-cut algorithminteger linear programmingILPcomputer experimentscluster editingfixed-parameter tractabilityNP-complete problemFPTalgorithm engineering

Mathematics Subject Classification ID

Integer programming (90C10) Nonnumerical algorithms (68W05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10)

Related Items (24)

Linear-time minimal cograph editing ⋮ Cluster Editing ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ On the complexity of multi-parameterized cluster editing ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ On making directed graphs transitive ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Unnamed Item ⋮ Sufficient conditions for edit-optimal clusters ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis ⋮ 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 ⋮ Branch-and-cut approaches for \(p\)-cluster editing ⋮ Branch-and-price for \(p\)-cluster editing ⋮ Cluster editing with locally bounded modifications ⋮ Parameterized algorithms for module map problems ⋮ The biclique partitioning polytope ⋮ Complexity of modification problems for reciprocal best match graphs ⋮ Best match graphs and reconciliation of gene trees with species trees ⋮ The Branch and Cut Method for the Clique Partitioning Problem ⋮ 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
• NP-hard problems in hierarchical-tree clustering
• A cutting plane algorithm for a clustering problem
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• On the partial order polytope of a digraph
• Clustering with qualitative information
• Clustering of microarray data via clique partitioning
• The Cluster Editing Problem: Implementations and Experiments
• A simple min-cut algorithm
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Going Weighted: Parameterized Algorithms for Cluster Editing

This page was built for publication: Exact algorithms for cluster editing: Evaluation and experiments