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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/1024 |
| Date | January 2004 |
| Creators | Williams, Aaron |
| Publisher | University of Waterloo |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Rights | Copyright: 2004, Williams, Aaron. All rights reserved. |
Page generated in 0.0015 seconds