215 citations · 689 across the 60 of their papers we have counts for
3 papers · 1 filter
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai +1
We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" al…
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai +3
Given a simple -vertex, -edge graph undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G…