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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Brand, Jan van den, Gholizadeh, Hossein, Jiang, Yonggang, de Vos, Tijn
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
by: Jiang, Yonggang, et al.
Published: (2025)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
by: Agarwal, Arpit, et al.
Published: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
by: Haeupler, Bernhard, et al.
Published: (2025)

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)

Distributed Sparsest Cut via Eigenvalue Estimation
by: Maus, Yannic, et al.
Published: (2025)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

Computing Flows in Subquadratic Space
by: Brand, Jan van den, et al.
Published: (2026)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
by: de Vos, Tijn, et al.
Published: (2024)

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
by: Cruciani, Emilio, et al.
Published: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

Minimum-Peak-Cost Flows Over Time
by: Anapolska, Mariia, et al.
Published: (2025)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Dynamic Rank, Basis, and Matching
by: Brand, Jan van den, et al.
Published: (2026)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

DAG Projections: Reducing Distance and Flow Problems to DAGs
by: Haeupler, Bernhard, et al.
Published: (2026)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
by: Hua, Kevin, et al.
Published: (2024)

Minimum-Cost Network Flow with Dual Predictions
by: Chen, Zhiyang, et al.
Published: (2026)

Thin Trees for Near Minimum Cuts
by: Klein, Nathan, et al.
Published: (2026)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
by: Chhabra, Adil, et al.
Published: (2025)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Width Parameters for Minimum Flow Decomposition
by: Grigorjew, Andreas, et al.
Published: (2024)

The Power of Greedy for Online Minimum Cost Matching on the Line
by: Balkanski, Eric, et al.
Published: (2022)

Learning Minimum Linear Arrangement of Cliques and Lines
by: Dallot, Julien, et al.
Published: (2024)

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
by: Bampis, Evripidis, et al.
Published: (2024)

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
by: Kuo, Tung-Wei
Published: (2024)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

High Probability Work Efficient Parallel Algorithms
by: Hutton, Chase, et al.
Published: (2026)

Scheduling Jobs with Work-Inefficient Parallel Solutions
by: Kuszmaul, William, et al.
Published: (2024)