8 citations · 14 across the 18 of their papers we have counts for
26 papers · 1 filter
Strongly Polynomial Parallel Maximum Flow Revisited
Adam Karczmarz, Paweł Pilarski
We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with vertices and arcs, we show that a randomized paralle…
Fully Dynamic Algorithms for Transitive Reduction
Gramoz Goranci, Adam Karczmarz, Ali Momeni +1
Given a directed graph , a transitive reduction of (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of that preserves the reachability rela…
On Incremental Approximate Shortest Paths in Directed Graphs
Adam Górkiewicz, Adam Karczmarz
In this paper, we show new data structures maintaining approximate shortest paths in sparse directed graphs with polynomially bounded non-negative edge weights under edge insertion…
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…
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…
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…
Optimal Decremental Connectivity in Non-Sparse Graphs
Anders Aaman, Adam Karczmarz, Jakub Łącki +3
We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomiz…
Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
Adam Karczmarz
We revisit the problem of finding optimal strategies for deterministic Markov Decision Processes (DMDPs), and a closely related problem of testing feasibility of systems of lin…
Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems
Adam Karczmarz
We consider the directed minimum weight cycle problem in the fully dynamic setting. To the best of our knowledge, so far no fully dynamic algorithms have been designed specifically…
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…
Planar Reachability Under Single Vertex or Edge Failures
Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis
In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph ca…
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…
Min-Cost Flow in Unit-Capacity Planar Graphs
Adam Karczmarz, Piotr Sankowski
In this paper we give an time algorithm for computing min-cost flow (or min-cost circulation) in unit capacity planar multigraphs where edge costs…
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
Adam Karczmarz, Jakub Łącki
We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm f…
Decremental SPQR-trees for Planar Graphs
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +2
We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over operation…
Contracting a Planar Graph Efficiently
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +3
We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access…
Decremental Single-Source Reachability in Planar Digraphs
Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki +1
In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in $O(n\log^2{n}…
Improved Bounds for Shortest Paths in Dense Distance Graphs
Paweł Gawrychowski, Adam Karczmarz
We study the problem of computing shortest paths in so-called dense distance graphs. Every planar graph on vertices can be partitioned into a set of edge-disjoint…