Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorBisseling, R.H.
dc.contributor.authorHeuseveldt, J.
dc.date.accessioned2019-07-29T17:01:12Z
dc.date.available2019-07-29T17:01:12Z
dc.date.issued2019
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/33012
dc.description.abstractTo 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.
dc.description.sponsorshipUtrecht University
dc.format.extent410444
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.titlePruning of alternating-path trees for bipartite graph matching
dc.type.contentBachelor Thesis
dc.rights.accessrightsOpen Access
dc.subject.courseuuWiskunde


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record