<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T18:23:12Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/10971" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/10971</identifier><datestamp>2025-03-26T23:31:58Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Edmonds, Jack</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="98bfc032-9eec-4330-af8f-28569bfabdce" confidence="600">Pulleyblank, William R.</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2016-09-30T14:03:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2016-09-30T14:03:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2016-09-30</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">1973</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/10971</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Let G = (V, E, ~) be a finite loopless graph, let&#xd;
b=(bi:ieV) be a vector of positive integers. A&#xd;
feasible matching is a vector X = (x.: j e: E)&#xd;
J&#xd;
of nonnegative&#xd;
integers such that for each node i of G, the sum of the&#xd;
over the edges j of G incident with i is no&#xd;
greater than bi. The matching polyhedron P(G, b) is the&#xd;
convex hull of the set of feasible matchings.&#xd;
In Chapter 3 we describe a version of Edmonds&amp;apos; blossom&#xd;
algorithm which solves the problem of maximizing C • X&#xd;
over P (G, b) where c =. (c.: j e: E)&#xd;
J&#xd;
is an arbitrary real&#xd;
vector. This algorithm proves a theorem of Edmonds which&#xd;
gives a set of linear inequalities sufficient to define&#xd;
P(G, b).&#xd;
In Chapter 4 we prescribe the unique subset of these&#xd;
inequalities which are necessary to define P(G, b), that&#xd;
is, we characterize the facets of P(G, b). We also&#xd;
characterize the vertices of P(G, b), thus describing the&#xd;
structure possessed by the members of the minimal set X&#xd;
of feasible matchings of G such that for any real vector&#xd;
c = (c.: j e: E), c • x is maximized over P(G, b)&#xd;
J&#xd;
member of X.&#xd;
by a&#xd;
In Chapter 5 we present a generalization of the blossom&#xd;
algorithm which solves the problem: maximize c • x over&#xd;
a face F of P(G, b) for any real vector c = (c.: j e: E).&#xd;
J&#xd;
In other words, we find a feasible matching x of G which&#xd;
satisfies the constraints obtained by replacing an arbitrary&#xd;
subset of the inequalities which define P(G, b) by equations and which maximizes c • x subject to this&#xd;
restriction. We also describe an application of this&#xd;
algorithm to matching problems having a hierarchy of objective&#xd;
functions, so called &amp;apos;&amp;apos;multi-optimization&amp;apos;&amp;apos; problems.&#xd;
In Chapter 6 we show how the blossom algorithm can be&#xd;
combined with relatively simple initialization algorithms&#xd;
to give an algorithm which solves the following postoptimality&#xd;
problem. Given that we know a matching 0 x £ P(G, b)&#xd;
maximizes c · x over P(G, b), we wish to utilize 0&#xd;
X&#xd;
which&#xd;
to&#xd;
find a feasible matching x&amp;apos; £ P(G, b&amp;apos;) which maximizes&#xd;
c • x over P(G, b&amp;apos;), where b&amp;apos; = (b!: i £ V)&#xd;
]_&#xd;
vector of positive integers and&#xd;
arbitrary real vector.&#xd;
c=(c.:j£E)&#xd;
J&#xd;
is a&#xd;
is an&#xd;
In Chapter 7 we describe a computer implementation of&#xd;
the blossom algorithm described herein.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">set theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">polyhedral theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">first facet characterization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">second facet characterization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">vertices of polyhedra</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Blossom algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">alternating forests</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Hungarian forests</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Post-Optimality algorithm</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">FACES OF MATCHING POLYHEDRA</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Edmonds, Jack</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>