research
∙
08/17/2023
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Algebraic techniques have had an important impact on graph algorithms so...
share
research
∙
03/31/2022
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
We study reachability and shortest paths problems in dynamic directed gr...
research
∙
11/17/2021
Optimal Decremental Connectivity in Non-Sparse Graphs
We present a dynamic algorithm for maintaining the connected and 2-edge-...
research
∙
10/28/2021
Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
We revisit the problem of finding optimal strategies for deterministic M...
research
∙
08/09/2021
Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf
Shapley values are one of the main tools used to explain predictions of ...
research
∙
06/22/2021
Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems
We consider the directed minimum weight cycle problem in the fully dynam...
research
∙
03/17/2021
Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs
We consider the problem of computing shortest paths in weighted unit-dis...
research
∙
03/05/2021
Decomposable Submodular Function Minimization via Maximum Flow
This paper bridges discrete and continuous optimization approaches for d...
research
∙
01/07/2021
Planar Reachability Under Single Vertex or Edge Failures
In this paper we present an efficient reachability oracle under single-e...
research
∙
01/07/2021
A Deterministic Parallel APSP Algorithm and its Applications
In this paper we show a deterministic parallel all-pairs shortest paths ...
research
∙
07/04/2019
Min-Cost Flow in Unit-Capacity Planar Graphs
In this paper we give an O((nm)^2/3 C) time algorithm for computing min-...
research
∙
07/04/2019
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
We give new partially-dynamic algorithms for the all-pairs shortest path...
research
∙
06/28/2018