Fast Vertex Merging for Cluster Editing

Bachelor thesis (2021)

Authors

L.H.C. Holten Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (mentor)
J.A. Pouwelse Data-Intensive Systems - EEMCS (coach)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Lucas Holten
More Info
expand_more

Published Date

01-07-2021

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

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.

Files

Paper_Final.pdf
(.pdf | 0.307 Mb)