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).