KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficient Parallel and External Matching

Birn, Marcel; Osipov, Vitaly; Sanders, Peter; Schulz, Christian; Sitchinava, Nodari

Abstract (englisch):
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 log2𝑛

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.

DOI: 10.1007/978-3-642-40047-6_66
Zitationen: 9
Zitationen: 9
Zugehörige Institution(en) am KIT Institut fĂŒr Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2013
Sprache Englisch
Identifikator ISBN: 978-3-642-40047-6
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097633
Erschienen in Euro-Par 2013 - Parallel Processing. Ed.: F. Wolf
Verlag Springer Verlag
Seiten 659-670
Serie Lecture Notes in Computer Science ; 8097
Nachgewiesen in Scopus
KIT – Die ForschungsuniversitĂ€t in der Helmholtz-Gemeinschaft
KITopen Landing Page