Pruning of alternating-path trees for bipartite graph matching
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.