215 citations · 582 across the 17 of their papers we have counts for
17 papers
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster, Gramoz Goranci
Spanning trees of low average stretch on the non-tree edges, as introduced by Alon et al. [SICOMP 1995], are a natural graph-theoretic object. In recent years, they have found sign…
A Note on Hardness of Diameter Approximation
Karl Bringmann, Sebastian Krinninger
We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, rounds are necessary to compute the diameter [Fri…
Decremental Data Structures for Connectivity and Dominators in Directed Graphs
Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano +2
We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repert…
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with nodes and edges. This problem has a long history in combinatorial optim…
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with total up…
Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Ittai Abraham, Shiri Chechik, Sebastian Krinninger
We revisit the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph. The allowed updates are insertions and deletions o…
Fully Dynamic Spanners with Worst-Case Update Time
Greg Bodwin, Sebastian Krinninger
An -spanner of a graph is a subgraph such that preserves all distances of within a factor of . In this paper, we give fully dynamic algorithms for ma…
Polynomial-Time Algorithms for Energy Games with Special Weight Structures
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger +1
Energy games belong to a class of turn-based two-player infinite-duration games}played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems tha…
On Fully Dynamic Graph Sparsifiers
Ittai Abraham, David Durfee, Ioannis Koutis +2
We initiate the study of dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polyl…
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
In the decremental single-source shortest paths (SSSP) problem we want to maintain the distances between a given source node and every other node in an -node -edge graph…
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of commun…
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai +1
Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an matrix and will receive column-vectors of size , denoted by $v_1,…
Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on -node -edge directed graphs under edge…
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
We present a deterministic -approximation -time algorithm for solving the single-source shortest paths problem on distributed weighted networks…
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer
We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph, which are straightforward generalizations of strongly connecte…
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
We study dynamic -approximation algorithms for the all-pairs shortest paths problem in unweighted undirected -node -edge graphs under edge deletions. The fastest algor…
Approximating the minimum cycle mean
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger +1
We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean wei…