Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
- 1 February 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (1) , 140-150
- https://doi.org/10.1137/0221011
Abstract
In this paper we use interior-point methods for linear programming, developed in the contextof sequential computation, to obtain a parallel algorithm for the bipartite matching problem.Our algorithm finds a maximum cardinality matching in a bipartite graph with n nodes andm edges in O(pm log3n) time on a CRCW PRAM. Our results extend to the weighted bipartitematching problem and to the zero-one minimum-cost flow problem, yielding O(pm log2n log nC)algorithms, where C ? ...Keywords
This publication has 10 references indexed in Scilit:
- Interior path following primal-dual algorithms. part I: Linear programmingMathematical Programming, 1989
- A polynomial-time algorithm, based on Newton's method, for linear programmingMathematical Programming, 1988
- Matching is as easy as matrix inversionCombinatorica, 1987
- Constructing a perfect matching is in random NCCombinatorica, 1986
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- A fast parallel algorithm for routing in permutation networksIEEE Transactions on Computers, 1981
- Parallel Prefix ComputationJournal of the ACM, 1980
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- Using euler partitions to edge color bipartite multigraphsInternational Journal of Parallel Programming, 1976