Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A generalization of Hopcroft-Karp algorithm for semi-matchings and
  covers in bipartite graphs (Maximum semi-matching problem in bipartite
  graphs)   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)$.

4
The categories of this paper are: cond-mat
31
The categories of this paper are: ao-sci
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex
18
The categories of this paper are: econ
22
The categories of this paper are: chao-dyn
2
The categories of this paper are: math
33
The categories of this paper are: plasm-ph
9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
30
The categories of this paper are: q-alg
25
The categories of this paper are: patt-sol
37
The categories of this paper are: supr-con
35
The categories of this paper are: mtrl-th
3
The categories of this paper are: physics
20
The categories of this paper are: acc-phys