Back to search

University of Waterloo

Packing Directed Joins

Abstract

dc:description.abstract

Edmonds and Giles conjectured that the maximum number of directed joins in a packing is equal to the minimum weight of a directed cut, for any weighted directed graph. This is a generalization of Woodall's Conjecture (which is still open). Schrijver found the first known counterexample to the Edmonds-Giles Conjecture, while Cornuejols and Guenin found the next two. In this thesis we introduce new counterexamples, and prove that all minimal counterexamples of a certain type have now been found.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Williams, Aaron

Subjects

dc:subject × 7

Rights

dc:rights
Statement dc:rights
  • Copyright: 2004, Williams, Aaron. All rights reserved.
Language dc:language.iso
en

Identifiers

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

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

Williams, Aaron. Packing Directed Joins. University of Waterloo, 2004. http://hdl.handle.net/10012/1024