2 citations · 3 across the 6 of their papers we have counts for
8 papers
Faster Randomized and Deterministic k-Clustering on Graphs
Sebastian Forster, Yasamin Nazari, Rajath Rao K. N. +1
In this paper, we study the -clustering and -center problems on graphs, where -clustering generalizes the -median () and -means () problems. We obt…
Adaptive Fully Dynamic -Center Clustering with (Near-)Optimal Worst-Case Guarantees
Mara Grilnberger, Antonis Skarlatos
Given a sequence of adversarial point insertions and point deletions, is it possible to simultaneously optimize the approximation ratio, update time, and recourse for a -cluster…
Incremental (k, z)-Clustering on Graphs
Emilio Cruciani, Sebastian Forster, Antonis Skarlatos
Given a weighted undirected graph, a number of clusters , and an exponent , the goal in the -clustering problem on graphs is to select vertices as centers that mi…
Dynamic Consistent -Center Clustering with Optimal Recourse
Sebastian Forster, Antonis Skarlatos
Given points from an arbitrary metric space and a sequence of point updates sent by an adversary, what is the minimum recourse per update (i.e., the minimum number of changes neede…
Dynamic algorithms for k-center on graphs
Emilio Cruciani, Sebastian Forster, Gramoz Goranci +2
In this paper we give the first efficient algorithms for the -center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into…
Fast Algorithms for Energy Games in Special Cases
Sebastian Forster, Antonis Skarlatos, Tijn de Vos
In this paper, we study algorithms for special cases of energy games, a class of turn-based games on graphs that show up in the quantitative analysis of reactive systems. In an ene…
Bootstrapping Dynamic Distance Oracles
Sebastian Forster, Gramoz Goranci, Yasamin Nazari +1
Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the central problems in dynamic graph algorithms. Despite extensive research on this topic,…
Computing Smallest Convex Intersecting Polygons
Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak +1
A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of comput…