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

Abstract

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 each vertex $v\in 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\le m$, constructs a maximum $(f,g)$-semi-matching in running time $O(m\cdot \min (\sqrt{{\sum }_{u\in U}f(u)},\sqrt{{\sum }_{v\in V}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(\sqrt{n}m\log n)$.

Cited by in corpus (3)

• Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization
• Decreasing Minimization on M-convex Sets: Algorithms and Applications
• Decreasing Minimization on M-convex Sets: Background and Structures