215 citations · 792 across the 83 of their papers we have counts for
91 papers · 1 filter
Incremental Exact Vertex Connectivity
Felix Adena, Monika Henzinger, Christoph Kern +1
We study the problem of maintaining the vertex connectivity of a graph under edge insertions. For undirected graphs, our algorithm uses amortized time per edg…
Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
Antoine El-Hayek, Monika Henzinger, Jason Li
Dynamically maintaining the minimum cut in a graph under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound…
Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
Monika Henzinger, Jason Li, Satish Rao +1
In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time which he termed near-linear time meaning linear (…
On -Matching and Fully-Dynamic Maximum -Edge Coloring
Antoine El-Hayek, Kathrin Hanauer, Monika Henzinger
Given a graph that is modified by a sequence of edge insertions and deletions, we study the Maximum -Edge Coloring problem Having access to colors, how can we color as m…
Differential Privacy for Clustering Under Continual Observation
Max Dupré la Tour, Monika Henzinger, David Saulpic
We consider the problem of clustering privately a dataset in that undergoes both insertion and deletion of points. Specifically, we give an -differentia…
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Monika Henzinger, Barna Saha, Martin P. Seybold +1
{\em Algorithms with predictions} incorporate machine learning predictions into algorithm design. A plethora of recent works incorporated predictions to improve on worst-case optim…