KIT | KIT-Bibliothek | Impressum

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 ... mehr

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