Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
ACM Transactions on Parallel Computing · 05.08.2026
DOI: 10.1145/3833219 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, online erschienen am 05.08.2026. Verfasst von Jan van den Brand und 3 weiteren Autor:innen. Die Arbeit nennt 78 Literaturangaben.
Abstract (Originalsprache)
For n -vertex m -edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with \(\tilde{O}(m+n^ {1.5}) \) work and \(\tilde{O}(\sqrt {n}) \) depth. On moderately dense graphs ( m > n 1.5 ), our algorithm is the first one to achieve both near-linear work and sub-linear depth. Previous algorithms are either achieving almost optimal work but are highly sequential [18], or achieving sub-linear depth but use super-linear work [49, 62]. Our result also leads to improvements for the special cases of max flow, bipartite maximum matching, shortest paths, and reachability. Notably, the previous algorithms achieving near-linear work for shortest paths and reachability all have depth \(n^{o(1)}\cdot \sqrt {n} \) [26, 33]. Our algorithm consists of a parallel implementation of [11]. One important building block is a parallel batch-dynamic expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [17]. Other versions. An extended abstract of this paper was previously published in the Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2025.
Zitieren
APA
Brand, J. V. D., Gholizadeh, H., Jiang, Y., & Vos, T. D. (2026). Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances. ACM Transactions on Parallel Computing. https://doi.org/10.1145/3833219
Vancouver
Brand JVD, Gholizadeh H, Jiang Y, Vos TD. Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances. ACM Transactions on Parallel Computing. 2026. doi:10.1145/3833219
BibTeX
@article{Brand2026,
author = {Brand, Jan van den and Gholizadeh, Hossein and Jiang, Yonggang and Vos, Tijn de},
title = {Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances},
journal = {ACM Transactions on Parallel Computing},
year = {2026},
doi = {10.1145/3833219}
}
EUVIMED