5 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…
A General Reduction from Near-Additive Emulators to Near-Exact Hopsets
Julian Aeri, Sebastian Forster, Mara Grilnberger
Graph emulators and hopsets are two fundamental concepts for distance approximation. When the multiplicative stretch is for arbitrarily small , these structures are kn…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
Fully Dynamic Spectral Sparsification for Directed Hypergraphs
Sebastian Forster, Gramoz Goranci, Ali Momeni
There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully d…
Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
Emilio Cruciani, Sebastian Forster, Tijn de Vos
We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact of their neighbors instead of a single one during both PUSH and PULL oper…