A fast parallel algorithm for minimum-cost small integral flows
From MaRDI portal
Publication:2354029
DOI10.1007/s00453-013-9865-1zbMath1318.90017arXiv1210.0340MaRDI QIDQ2354029
Publication date: 10 July 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1210.0340
parallel algorithms; time complexity; randomized algorithms; minimum-cost flow; processor complexity; maximum integral flow; polynomial verification
68Q25: Analysis of algorithms and problem complexity
90B10: Deterministic network models in operations research
68W10: Parallel algorithms in computer science
68W20: Randomized algorithms
Related Items
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
