Aug 2026· Embedded Systems and Applications· pp. 147:1-147:16· 0 citations· 46 references
Computer Science
TL;DR
This work shows that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and V\'egh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth, which improves upon the previously described tradeoffs between work and depth.
Abstract
We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and V\'egh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].
This paper achieves truly work-efficient parallel derandomization by obtaining linear work bounds of $O(m+n)$, thereby achieving truly work-efficient parallel derandomization.
This paper presents the first distributed near-optimal $\tilde O(D)$-rounds $(1-o(1))$-approximation algorithm for Maximum $st$-Flow in general undirected planar graphs.
Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann· 0 citations
The minimum $k$-cut problem asks for the fewest edges whose removal leaves an input graph with at least $k$ connected components. Previously, the best algorithm for simple graphs ran in $O_k(n^{(1-\varepsilon)k+O(1)})$ time~\cite{HL22}, showing that the \(n^k\) barrier can be broken up to a polynomial overhead. We give...
We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or ind...
The first $poly(\Delta,\log n)-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model is presented and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin· 0 citations
The Minimum $k$-Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least $k$ connected components. We consider only $k \ge 3$. Under the Max-Weight Clique conjecture, weighted Minimum $k$-Cut requires $n^{k-1-o(1)}$ time for every fixed $k$. The fastest previous...
Trevor Vaughn· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
