@inproceedings{b383246e73f34e029749f6cea6bf3cd9,

title = "Almost-optimum speed-ups of algorithms for dipartite matching and relatod problems",

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.",

author = "Gabow, {Harold N.} and Tarjan, {Robert E.}",

year = "1988",

doi = "10.1145/62212.62263",

language = "English (US)",

isbn = "0897912640",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "514--527",

booktitle = "Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988",

note = "20th Annual ACM Symposium on Theory of Computing, STOC 1988 ; Conference date: 02-05-1988 Through 04-05-1988",

}