Almost-Optimum Parallel Speed-ups of Algorithms for Bipartite Matching and Related Problems
Report ID: TR-223-89Author: Tarjan, Robert E. / Gabow, Harold N.
Date: 1989-01-00
Pages: 33
Download Formats: |PDF|
Abstract:
This paper focuses on algorithms for matching problems that run on an EREW PRAM with p processors. ... Extensions of the algorithm are given, including an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs).