Practical Algorithmic Optimizations for Finding Maximal Matchings in Induced Subgraphs of Grids and Minimum Cost Perfect Matchings in Bipartite Graphs

Abstract

In this paper we present practical algorithmic optimizations addressing two problems. The first one is concerned
with computing a maximal matching in an induced subgraph of a grid graph. For this problem we present a faster
sequential algorithm using bit operations and a way of implementing it in a parallel environment. The second problem
is concerned with computing minimum cost perfect matchings in bipartite graphs. For this problem we extend the
idea behind the Hopcroft-Karp maximum matching algorithm and then we consider a more general situation in which
multiple minimum cost perfect matchings need to be computed in the same graph, under certain cost restrictions. We
present experimental results for all the proposed optimizations.