EUVIMEDEUVIMED entdecken
Crossref

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances

Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, Tijn de Vos

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →