@inproceedings{sitchinava-europar13,
  author = "Marcel Birn and Vitaly Osipov and Peter Sanders and Christian Schulz and Nodari Sitchinava",
  title  = "Efficient parallel and external matching", 
  booktitle = "Proceedings of the 19th European Conference on Parallel Processing",
  series = "Euro-Par '13",
  pages = "659-670", 
  year = 2013,
  month = 8,
  doi = "10.1007/978-3-642-40047-6_66",
  arxiv = "https://arxiv.org/abs/1302.4587",
  abstract = "We study a simple parallel algorithm for computing matchings in a graph. A variant for unweighted graphs finds a maximal matching using linear expected work and $O(\log^2 n)$ expected running time in the CREW PRAM model. Similar results also apply to External Memory, MapReduce and distributed memory models. In the maximum weight case the algorithm guarantees a 1/2-approximation. Although the parallel execution time is linear for worst case weights, an experimental evaluation indicates good scalabilty on distributed memory machines and on GPUs. Furthermore, the solution quality is very good in practice."
}