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

        Pruning of alternating-path trees for bipartite graph matching

        Thumbnail
        View/Open
        Scriptie_augtree_pruning.pdf (400.8Kb)
        Publication date
        2019
        Author
        Heuseveldt, J.
        Metadata
        Show full item record
        Summary
        To compute a maximum matching in a bipartite graph we can use algorithms based on augmenting paths. If a search for an augmenting path is unsuccessful, the information gained by the search is often discarded. However, it is possible to use this information to speed up future searches. In this thesis we will formally prove that it is possible to prune exhausted parts of the graph, for both single-source (SS) and multi-source (MS) breadth-first-search (BFS) algorithms. Our implementation gives a speedup for the SS-BFS algorithm. Due to additional overhead, the MS-BFS algorithm is more often slowed down by the pruning rather than sped up.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/33012
        Collections
        • Theses
        Utrecht university logo