5 citations · 6 across the 3 of their papers we have counts for
3 papers
cs.DS2020
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…
cs.DS2019★ 1 cited
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…
cs.DS2019★ 5 cited
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…