Abstract
We present algorithms for matching and related problems that, run on an EREW PRAM with p processors. Given is a bipartite graph G with n vertices, m edges, and integral edge costs at most N in magnitude. We give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in O(√nm log(nN)(log(2))) time and 0(m) space, for p ≤ m/(√nog2n). For p = 1 this improves the best known sequential algorithm, and is within a factor of log(nN) of the best known bound for the problem without costs (maximum cardinality matching). For p < 1 the time is within a factor of logp of optimum speed-up. Extensions include 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). Our ideas also extend to general graph matching problems.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988 |
Publisher | Association for Computing Machinery |
Pages | 514-527 |
Number of pages | 14 |
ISBN (Print) | 0897912640, 9780897912648 |
DOIs | |
State | Published - Jan 1 1988 |
Event | 20th Annual ACM Symposium on Theory of Computing, STOC 1988 - Chicago, IL, United States Duration: May 2 1988 → May 4 1988 |
Other
Other | 20th Annual ACM Symposium on Theory of Computing, STOC 1988 |
---|---|
Country/Territory | United States |
City | Chicago, IL |
Period | 5/2/88 → 5/4/88 |
All Science Journal Classification (ASJC) codes
- Software