Efficient parallel and sequential algorithms for computing maximal and approximate maximum weight matchings in graphs.
The local max algorithm computes a maximal matching that provides a 1/2-approximation of the maximum weight matching. It runs with linear expected work and adapts to sequential, MPI, MapReduce, and external memory models.
| Repository | Description |
|---|---|
| LocalMaxMatching | Implementations of local max matching, Karp-Sipser, and tree matching algorithms |
Marcel Birn, Vitaly Osipov, Peter Sanders, Christian Schulz, Nodari Sitchinava. Efficient Parallel and External Matching. Euro-Par 2013. [arXiv] [DOI]