View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Approximating the maximum weight matching problem using the GraphBLAS standard

        Thumbnail
        View/Open
        Master_thesis.pdf (1.185Mb)
        Publication date
        2022
        Author
        Kemper, Jetske
        Metadata
        Show full item record
        Summary
        The maximum weight matching problem for general graphs is a well-studied problem with a variety of approximation algorithms already existing. Yet, many of them are hard to parallelize. Therefore, we propose a 3/4-approximation algorithm completely built on matrix operations in GraphBLAS. The idea is that these operations are more straightforward to parallelize. The algorithm is based on finding and flipping positive-gain augmentations.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/41451
        Collections
        • Theses
        Utrecht university logo