Almost-optimum speed-ups of algorithms for dipartite matching and relatod problems

Harold N. Gabow, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988
PublisherAssociation for Computing Machinery
Pages514-527
Number of pages14
ISBN (Print)0897912640, 9780897912648
DOIs
StatePublished - Jan 1 1988
Event20th Annual ACM Symposium on Theory of Computing, STOC 1988 - Chicago, IL, United States
Duration: May 2 1988May 4 1988

Other

Other20th Annual ACM Symposium on Theory of Computing, STOC 1988
CountryUnited States
CityChicago, IL
Period5/2/885/4/88

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Almost-optimum speed-ups of algorithms for dipartite matching and relatod problems'. Together they form a unique fingerprint.

  • Cite this

    Gabow, H. N., & Tarjan, R. E. (1988). Almost-optimum speed-ups of algorithms for dipartite matching and relatod problems. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988 (pp. 514-527). Association for Computing Machinery. https://doi.org/10.1145/62212.62263