KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficient Parallel and External Matching

Birn, Marcel 1; Osipov, Vitaly 1; Sanders, Peter 1; Schulz, Christian 1; Sitchinava, Nodari 1
1 Karlsruher Institut für Technologie (KIT)

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: 13
Zitationen: 12
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 Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page