12 citations · 12 across the 1 of their papers we have counts for
7 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…