Maximum weighted matching on a GPU
Master thesis
View/ Open
Date
2020-11-12Metadata
Show full item recordCollections
- Master theses [197]
Abstract
In this thesis we give the first parallel GPU-implementation of the ROMA algorithm suited for complete graphs. ROMA is an approximation algorithm solving the maximum weighted matching problem. Our algorithm achieves an average speedup of 207 on our input graphs when comparing it to the sequential algorithm, while still giving equally good matchings.