215 citations · 689 across the 60 of their papers we have counts for
6 papers · 1 filter
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…
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai +1
While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of {\em both} time and space, not much was known about achieving such type…