Maximilian Probst

collaborators

2 papers

cs.DS2019

Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time

Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen

Computing the Strongly-Connected Components (SCCs) in a graph $G = (V, E)$ is known to take only $O (m + n)$ time using an algorithm by Tarjan from 1972[SICOMP 72] where $m = ∣ E ∣$ , $n=…

cs.DS2018

On the complexity of the (approximate) nearest colored node problem

Maximilian Probst

Given a graph $G = (V, E)$ where each vertex is assigned a color from the set $C = {c_{1}, c_{2}, .., c_{σ}}$ . In the (approximate) nearest colored node problem, we want to query, given $v…