Open Collections

UBC Theses and Dissertations

UBC Theses Logo
Featured Collection

UBC Theses and Dissertations

Matchings with a size constraint Zhou, Bo

Abstract

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 Metadata

Title
Matchings with a size constraint
Creator
Zhou, Bo
Publisher
University of British Columbia
Date Issued
1990
Description
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.
Genre
Thesis/Dissertation
Type
Text
Language
eng
Date Available
2010-10-21
Provider
Vancouver : University of British Columbia Library
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
DOI
10.14288/1.0080433
URI
http://hdl.handle.net/2429/29413
Degree (Theses)
Master of Science - MSc
Program (Theses)
Mathematics
Affiliation
Science, Faculty of; Mathematics, Department of
Degree Grantor
University of British Columbia
Campus
UBCV
Scholarly Level
Graduate
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.