8 citations · 14 across the 18 of their papers we have counts for
6 papers · 1 filter
Towards Scalable and Practical Batch-Dynamic Connectivity
Quinten De Man, Laxman Dhulipala, Adam Karczmarz +3
We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for t…
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz
In the restricted shortest paths problem, we are given a graph whose edges are assigned two non-negative weights: lengths and delays, a source , and a delay threshold . T…
Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
Adam Karczmarz, Da Wei Zheng
Le and Wulff-Nilsen [SODA '24] initiated a systematic study of VC set systems to unweighted -minor-free directed graphs. We extend their results in the following ways: $\bulle…
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…
Fully Dynamic Strongly Connected Components in Planar Digraphs
Adam Karczmarz, Marcin Smulewicz
In this paper, we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintainin…
Accurate estimation of feature importance faithfulness for tree models
Mateusz Gajewski, Adam Karczmarz, Mateusz Rapicki +1
In this paper, we consider a perturbation-based metric of predictive faithfulness of feature rankings (or attributions) that we call PGI squared. When applied to decision tree-base…