Almost-Optimum Parallel Speed-Ups of Algorithms for Bipartite Matching and Related Problems.

摘要

This paper focuses on algorithms for matching problems that run on an EREW PRAM with p processors. Given is a bipartite graph with n vertices, m edges, and integral edge costs at most N in magnitude. This bound is within a factor of log p of optimum speed-up of the best known sequential algorithm, which in turn is within a factor of log (nN) of the best known bound for the problem without costs (maximum cardinality matching). 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). (KR)