Papers accepted at ISAAC'24

Two of our papers are accepted at the International Symposium on Algorithms and Computation (ISAAC'24).

The paper When Can Cluster Deletion with Bounded Weights Be Solved Efficiently? is written by members of our group, and considers the parameterized complexity of the weighted version of the graph clustering problem Cluster Deletion parameterized by the largest assigned edge weight. 
Among other results, the paper presents an algorithm to solve the considered problem in polynomial time on specific graph classes, if the largest assigned weight is small.

The paper Complexity of Local Search for Euclidean Clustering Problems is written by Bodo Manthey (University of Twente), Nils Morawietz (Friedrich Schiller University Jena), Jesse van Rhijn (University of Twente) and Frank Sommer (TU Wien) and shows that finding locally optimal solutions for the k-Means problem in Euclidean spaces presumably cannot be done in polynomial time, even when considering the arguably most simple local neighborhood for this problem.