27 citations · 82 across the 20 of their papers we have counts for
24 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 know…
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…
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…
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…
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…
On Dynamic Graph Algorithms with Predictions
Jan van den Brand, Sebastian Forster, Yasamin Nazari +1
We study dynamic algorithms in the model of algorithms with predictions. We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predic…
Fast 2-Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yael Kirkpatrick +3
In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for -approximate A…
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…
The Laplacian Paradigm in Deterministic Congested Clique
Sebatian Forster, Tijn de Vos
In this paper, we bring the techniques of the Laplacian paradigm to the congested clique, while further restricting ourselves to deterministic algorithms. In particular, we show ho…
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,…
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update tim…
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yasamin Nazari +1
We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with edges and nodes unde…
The Laplacian Paradigm in the Broadcast Congested Clique
Sebastian Forster, Tijn de Vos
In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic n…
Faster Cut Sparsification of Weighted Graphs
Sebastian Forster, Tijn de Vos
A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of . This paper considers computing cu…
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
Sebastian Forster, Martin Grösbacher, Tijn de Vos
Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter…
Fast Deterministic Fully Dynamic Distance Approximation
Jan van den Brand, Sebastian Forster, Yasamin Nazari
In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain imp…
Minor Sparsifiers and the Distributed Laplacian Paradigm
Sebastian Forster, Gramoz Goranci, Yang P. Liu +3
We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrice…
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
Sebastian Forster, Gramoz Goranci, Monika Henzinger
We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for weighted graphs undergoing edge insertions and deletions. We obtain a trade-off between amort…
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak +2
Consider the following "local" cut-detection problem in a directed graph: We are given a seed vertex and need to remove at most edges so that at most edges can be reach…
A Faster Local Algorithm for Detecting Bounded-Size Cuts with Applications to Higher-Connectivity Problems
Sebastian Forster, Liu Yang
Consider the following "local" cut-detection problem in a directed graph: We are given a starting vertex and need to detect whether there is a cut with at most edges crossi…
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Aaron Bernstein, Sebastian Forster, Monika Henzinger
Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, wher…
A Faster Distributed Single-Source Shortest Paths Algorithm
Sebastian Forster, Danupon Nanongkai
We devise new algorithms for the single-source shortest paths (SSSP) problem with non-negative edge weights in the CONGEST model of distributed computing. While close-to-optimal so…
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Sebastian Forster, Andreas Karrenbauer +1
We present a method for solving the transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of in undirected graphs w…