215 citations · 689 across the 60 of their papers we have counts for
4 papers · 1 filter
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…
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and -Time
Danupon Nanongkai, Thatchaphol Saranurak
We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee {\em worst-case update time} a…
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…
New Deterministic Approximation Algorithms for Fully Dynamic Matching
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a -approximate maximum matching in general graphs with $O(\…