8 papers
Constrained Correlation Clustering: Towards Optimality
Sina Azizeddin, Evangelos Kipouridis, Nithin Varma
In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the number of violated pa…
Faster algorithms for k-Orthogonal Vectors in low dimension
Anita Dürr, Evangelos Kipouridis, Michael Lampis +1
In the Orthogonal Vectors problem (OV), we are given two families of subsets of , each of size , and the task is to decide whether there exists a pair $a…
Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas +2
Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2…
Dynamic data structures for twin-ordered matrices
BartÅomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…
A Broader View on Clustering under Cluster-Aware Norm Objectives
Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase
We revisit the -clustering problem that we introduced in a recent work [SODA'25], and which subsumes fundamental clustering problems such as -Center, -Median, Min-Sum…
Fitting Tree Metrics and Ultrametrics in Data Streams
Amir Carmel, Debarati Das, Evangelos Kipouridis +1
Fitting distances to tree metrics and ultrametrics are two widely used methods in hierarchical clustering, primarily explored within the context of numerical taxonomy. Given a posi…