KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering Fast Parallel Matching Algorithms

Birn, Marcel


The computation of matchings has applications in the solving process of a large variety of problems, e.g. as part of graph partitioners. We present and analyze three sequential and two parallel approximation algorithms for the cardinality and weighted matching problem. One of the sequential algorithms is based on an algorithm by Karp and Sipser to compute maximal matchings [21]. Another one is based on the idea of locally heaviest edges by Preis [30]. The third sequential algorithm is a new algorithm based on the computation of maximum weighted matchings of trees spanning the input graph. We show for two of these algorithms that the runtime for slight variations of them is expected to be linear. However the experimental results suggest that this is also the case for the unmodified versions. The comparison with other approximate matching algorithms show that the computed matchings have a similar quality or even the same quality. On the other hand two of our the algorithms are much faster. For two of the sequential algorithms we show how to turn them into parallel matching algorithms. We show that for a simple non optimal partitioning of the input graphs speedups can be observed using up to 1024 processors. ... mehr

Volltext §
DOI: 10.5445/IR/1000058828
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2012
Sprache Englisch
Identifikator urn:nbn:de:swb:90-588286
KITopen-ID: 1000058828
Verlag Karlsruher Institut für Technologie (KIT)
Umfang 125 S.
Art der Arbeit Abschlussarbeit - Diplom
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page