- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Matching theory: subgraphs with degree constraints...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Matching theory: subgraphs with degree constraints and other properties Nam, Yunsun
Abstract
In this thesis, three generalizations of the matching problem are considered. The first problem is the existence of matrices with given row and column sums. This problem can be interpreted as the f-factor problem of a bipartite graph. The well-known existence theorem follows from maxfiow-mincut theorem, but it contains an exponential number (in the number of rows) of inequalities. We generalize the Gale-Ryser theorem and obtain some conditions under which this exponential number of inequalities can be reduced to a polynomial number of inequalities. The second problem is the general factor problem. Let G = (V, E) be a multigraph. An arbitrary subset BL, of {O, 1,2,. . . , deg(v)} is assigned to each vertex ʋ E Ʋ. We call a B-factor a spanning subgraph F of G such that deg (ʋ) ∈ Bv for every vertex ʋ ∈ V. A set B is said to have a gap of length p ≥1 if there exists an integer k such that k+ 1,.•.,k+p ∉ Bv, and yet k,k+p+ 1 ∉ Bv. It’s known that the problem is NP-complete if we allow gaps of length more than one. We extend the algorithm of Cornuéjols for simple graphs and obtain a strongly polynomial algorithm for finding a B-factor when each Bv doesn’t have a gap of length 2 or more. A new augmenting walk that need not alternate is introduced. The third problem is the square-free two-factor problem. A square-free two-factor is a two-factor in which the cycles don’t have length 4, i.e. are not squares. We obtain an augmenting path theorem like Berge’s augmenting path theorem for a 1-matching. Also we obtain a polynomial algorithm for finding a square-free two-factor when the squares of G are vertex-disjoint.
Item Metadata
Title |
Matching theory: subgraphs with degree constraints and other properties
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1994
|
Description |
In this thesis, three generalizations of the matching problem are considered.
The first problem is the existence of matrices with given row and column sums. This
problem can be interpreted as the f-factor problem of a bipartite graph. The well-known
existence theorem follows from maxfiow-mincut theorem, but it contains an exponential
number (in the number of rows) of inequalities. We generalize the Gale-Ryser theorem
and obtain some conditions under which this exponential number of inequalities can be
reduced to a polynomial number of inequalities.
The second problem is the general factor problem. Let G = (V, E) be a multigraph.
An arbitrary subset BL, of {O, 1,2,. . . , deg(v)} is assigned to each vertex ʋ E Ʋ. We
call a B-factor a spanning subgraph F of G such that deg (ʋ) ∈ Bv for every vertex
ʋ ∈ V. A set B is said to have a gap of length p ≥1 if there exists an integer k such
that k+ 1,.•.,k+p ∉ Bv, and yet k,k+p+ 1 ∉ Bv. It’s known that the problem
is NP-complete if we allow gaps of length more than one. We extend the algorithm of
Cornuéjols for simple graphs and obtain a strongly polynomial algorithm for finding a
B-factor when each Bv doesn’t have a gap of length 2 or more. A new augmenting walk
that need not alternate is introduced.
The third problem is the square-free two-factor problem. A square-free two-factor is
a two-factor in which the cycles don’t have length 4, i.e. are not squares. We obtain an
augmenting path theorem like Berge’s augmenting path theorem for a 1-matching. Also
we obtain a polynomial algorithm for finding a square-free two-factor when the squares
of G are vertex-disjoint.
|
Extent |
2734822 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-04-08
|
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.0079982
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
1994-05
|
Campus | |
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.