A generalization of Hopcroft-Karp algorithm for semi-matchings and covers in bipartite graphs (Maximum semi-matching problem in bipartite graphs)

Ján Katrenic, Gabriel Semanisin

An $(f,g)$-semi-matching in a bipartite graph $G=(U\cup V,E)$ is a set of edges $M\subseteq E$ such that each vertex $u\in U$ is incident with at most $f(u)$ edges of $M$, and ea…