UBC Theses and Dissertations
Matchings with a size constraint Zhou, Bo
We study the matching problem and some variants such as b-matching and (g, f)-factors. This thesis aims at polynomial algorithms which in addition have other properties. In particular, we develop a polynomial algorithm which can find optimal solutions of each possible size for weighted matching problem, and a strongly polynomial algorithm which can find a (g, f)-factor of fixed size.
Item Citations and Data