Fast Vertex Merging for Cluster Editing
L.H.C. Holten (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Demirović – Mentor (TU Delft - Algorithmics)
JA Pouwelse – Coach (TU Delft - Data-Intensive Systems)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
FPT algorithms for cluster editing are relatively successful in practice, however there is still the need for a fast weighted graph data-structure that allows merging vertices and deleting edges while keeping track of a lower bound. This paper presents such a data-structure with at worst O(n2) time complexities for basic operations on graphs with n vertices. Furthermore an open-source implementation of the data-structure and an algorithm for cluster editing is provided, written in Rust for performance and readability.