Return to search

Packing Directed Joins

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.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/1024
Date January 2004
CreatorsWilliams, Aaron
PublisherUniversity of Waterloo
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
RightsCopyright: 2004, Williams, Aaron. All rights reserved.

Page generated in 0.0017 seconds