Metraipolis › archive › dc_7b28ea0cc3c2
Strongly Polynomial Parallel Maximum Flow Revisited — arXiv:2608.12171
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.12171
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T05:52:52.417Z
- SHA-256 of the archived text
ff948d0bbc3cfb018a21f1ad6ca664d8e4308908f7d07273a7c5e03012de8747- Stable URL of this page
https://metraipolis.com/documento/dc_7b28ea0cc3c2
How to cite
Strongly Polynomial Parallel Maximum Flow Revisited — arXiv:2608.12171 — arXiv (en), https://arxiv.org/abs/2608.12171 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7b28ea0cc3c2 (Metraipolis archive dc_7b28ea0cc3c2, sha256 ff948d0bbc3cfb018a21f1ad6ca664d8e4308908f7d07273a7c5e03012de8747)
BibTeX
@misc{dc7b28ea0cc3c2,
title = {Strongly Polynomial Parallel Maximum Flow Revisited — arXiv:2608.12171},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.12171},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7b28ea0cc3c2; sha256 ff948d0bbc3cfb018a21f1ad6ca664d8e4308908f7d07273a7c5e03012de8747},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.12171. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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égh [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].
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.12171 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:48:37.122Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).