[{"type":"paper-conference","title":"Efficient Parallel and External Matching","issued":{"date-parts":[["2013"]]},"page":"659-670","container-title":"Euro-Par 2013 - Parallel Processing. Ed.: F. Wolf","DOI":"10.1007\/978-3-642-40047-6_66","author":[{"family":"Birn","given":"Marcel"},{"family":"Osipov","given":"Vitaly"},{"family":"Sanders","given":"Peter"},{"family":"Schulz","given":"Christian"},{"family":"Sitchinava","given":"Nodari"}],"publisher":"Springer","publisher-place":"Berlin","ISBN":"978-3-642-40047-6","ISSN":"0302-9743, 1611-3349","collection-title":"Lecture Notes in Computer Science","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 \ue23blog2\ud835\udc5b\r\n\r\nexpected 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.","kit-publication-id":"1000097633"}]