Alternating paths revisited II: restricted b-matchings in bipartite graphs

Abstract

We give a constructive proof for a min-max relation on restricted b-matchings in bipartite graphs, extending results of Hartvigsen, Király, and Frank. Restricted b-matching is a special case of covering pairs of sets, for which Benczúr and Végh constructed a polynomial time algorithm - this implies a polynomial time algorithm for restricted b-matchings, as well. In this paper we solve restricted b-matchings directly, in a conceptually simple way.

Bibtex entry:

@techreport{egres-05-13,
AUTHOR = {Pap, Gyula},
TITLE = {Alternating paths revisited {II}: restricted {\$b\$}-matchings in bipartite graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-13}
}