20 citations · 76 across the 29 of their papers we have counts for
10 papers · 1 filter
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
Maximilian Probst Gutenberg
In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edg…
Decremental APSP in Directed Graphs Versus an Adaptive Adversary
Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg +1
Given a directed graph , undergoing an online sequence of edge deletions with edges in the initial version of and , we consider the problem of maintaini…
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg +2
Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and…
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Let be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed sour…
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg +4
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees,…
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph undergoing edge deletions and a source vertex ; let $n =…
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Given a directed weighted graph undergoing vertex insertions \emph{and} deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that proc…
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Given a dynamic digraph undergoing edge deletions and given and , we consider the problem of maintaining -approximate shortest path distances from…
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
In the decremental -approximate Single-Source Shortest Path (SSSP) problem, we are given a graph with , undergoing edge deletions, and a distingu…
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph subject to edge insertions and deletions and a source vertex , and the goal is to…