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

Gyula Pap


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:

AUTHOR = {Pap, Gyula},
TITLE = {Alternating paths revisited {II}: restricted {$b$}-matchings in bipartite graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-13}

Last modification: 29.12.2020. Please email your comments to Tamás Király!