Maximum semi-matching problem in bipartite graphs
Ján Katrenič, Gabriel Semanišin · Discussiones Mathematicae Graph Theory · 2013
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{ u∈U f (u), v∈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( √ nm log n).