Parallel graph algorithm design is a very well studied topic. Many results have been presented for the PRAM model. However, these algorithms are inherently fine grained and experiments show that PRAM algorithms do often not achieve the expected speedup on real machines because of large message overheads. In this paper, we present coarse grained parallel graph algorithms with small message overheads that solve the following standard graph problems related to graph matching: finding maximum matchings in convex bipartite graphs, and finding maximum weight matchings in trees. To our knowledge, these are the first efficient parallel algorithms for these problems that are designed for standard commercial parallel machines such as off-the-shelf processor clusters.

Additional Metadata
Keywords Coarse grained parallel computing, Convex bipartite graph, Graph matching, Parallel algorithm, Unrooted tree
Persistent URL
Journal Parallel Computing
Chan, A. (Albert), Dehne, F, Bose, P, & Latzel, M. (Markus). (2008). Coarse grained parallel algorithms for graph matching. Parallel Computing, 34(1), 47–62. doi:10.1016/j.parco.2007.11.004