A fast parallel algorithm for minimum-cost small integral flows

DOI10.1007/s00453-013-9865-1zbMath1318.90017arXiv1210.0340OpenAlexW1924839147MaRDI QIDQ2354029

Andrzej Lingas, Mia Persson

Publication date: 10 July 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.0340

zbMATH Keywords

parallel algorithmstime complexityrandomized algorithmsminimum-cost flowprocessor complexitymaximum integral flowpolynomial verification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Related Items (1)

Derandomizing Isolation in Space-Bounded Settings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• The maximum flow problem is log space complete for P
• A probabilistic remark on algebraic program testing
• Improved processor bounds for combinatorial problems in RNC
• Parallel algorithms for the assignment and minimum-cost flow problems
• Maximal Flow Through a Network
• Faster Algebraic Algorithms for Path and Packing Problems
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Multiplying matrices faster than coppersmith-winograd
• Systems of distinct representatives and linear algebra

This page was built for publication: A fast parallel algorithm for minimum-cost small integral flows