62 citations · 316 across the 38 of their papers we have counts for
28 papers · 1 filter
Fully Dynamic Shortest Paths in Sparse Digraphs
Adam Karczmarz, Piotr Sankowski
We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with worst-ca…
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Adam Karczmarz, Piotr Sankowski
Algebraic techniques have had an important impact on graph algorithms so far. Porting them, e.g., the matrix inverse, into the dynamic regime improved best-known bounds for various…
Online matching with delays and stochastic arrival times
Mathieu Mari, Michał Pawłowski, Runtian Ren +1
This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In the original version of this p…
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
Adam Karczmarz, Anish Mukherjee, Piotr Sankowski
We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries ha…
Decomposable Submodular Function Minimization via Maximum Flow
Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee +2
This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide impro…
A Deterministic Parallel APSP Algorithm and its Applications
Adam Karczmarz, Piotr Sankowski
In this paper we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has work and $\tilde{O}(d…