2 citations · 2 across the 5 of their papers we have counts for
5 papers
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…
Exact Shortest Paths with Rational Weights on the Word RAM
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all t…
Max -Flow Oracles and Negative Cycle Detection in Planar Digraphs
Adam Karczmarz
We study the maximum -flow oracle problem on planar directed graphs where the goal is to design a data structure answering max -flow value (or equivalently, min -cut…
Deterministic Fully Dynamic SSSP and More
Jan van den Brand, Adam Karczmarz
We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2…
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…