A generalization of Hopcroft-Karp algorithm for semi-matchings and covers in bipartite graphs
Gabriel Semani · arXiv (Cornell University) · 2012
An (f;g)-semi-matching in a bipartite graph G = (U(V;E) is a set of edges M E such that each vertex u2 U is incident with at most f(u) edges of M, and each vertex v2 V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n m, constructs a maximum (f;g)- semi-matching in running time O(m min( q P u2U f(u); q P v2V g(v))). Using the reduction of (5) our result on maximum (f;g)-semi-matching problem directly implies an algorithm for the optimal semi-matching problem with running time O( p nm logn).