Back to search

University of Waterloo

SUBMODULAR FUNCTIONS, GRAPHS AND INTEGER POLYHEDRA

Abstract

dc:description.abstract

This thesis is a study of the faces of certain combinatorially ­defined polyhedra. In particular, we examine the vertices and facets of these polyhedra. Chapter 2 contains the essential mathematical background in polyhedral theory, linear programming and graph theory. We also discuss the existence of an integer-valued optimum solution to a linear program. This is essential for determining that the vertices of certain polyhedra are integer-valued, and for establishing related combinatorial min-max relations. Chapter 3 is the a application of the results of Chapter 4 to the polymatroid aspects of matroid theory. We characterize the vertices and the facets of the intersection of two matroid polyhedra. We use the characterization of the facets of this intersection to derive a graph theoretic description of the facets of the polyhedron associated with branchings in a graph. In Chapter 5 we discuss certain polyhedra which can be associated with strong k-covers and strong k-matchings of an acyclic graph. By proving the existence of integer¥valued optimum solutions to particular primal-dual pairs of linear programs we are able to demon­strate certain combinatorial min-max relations. Chapter 6 is a unification of the polyhedra described in Chapters 4 and 5, We give a combinatorial definition of a class of polyhedra which includes polymatroid intersection and the polyhedra associated with strong k-covers and strong k-matchings of an acyclic graph. We establish the existence of integer-valued optimum solutions to certain dual linear programs and thereby draw conclusions concerning the integrality of the vertices of particular polyhedra within this class. The applications include establishing the integrality of the vertices of the intersection of two integral polymatroids and the integrality of the vertices of strong k-cover and strong k-matching polyhedra. Chapter 7 is a discussion of the facets of polyhedra defined in Chapter 6 and we obtain a description of the facets of a subclass of these polyhedra which includes a description of the facets of the intersection of two polymatroids and the facets of strong k-cover and strong k-matching polyhedra.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Giles, Frederick Richard
Advisor dc:contributor.advisor
  • Edmonds, Jack

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/10835

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Giles, Frederick Richard. SUBMODULAR FUNCTIONS, GRAPHS AND INTEGER POLYHEDRA. University of Waterloo, 2016. http://hdl.handle.net/10012/10835