## 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/(√nog^{2}n). 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