Packing Directed Joins

Mathematics;directed graph;directed cut;directed join;min-max;Woodall"s Conjecture;Edmonds-Giles Conjecture

Williams, Aaron

University of Waterloo

关键词: Mathematics;    directed graph;    directed cut;    directed join;    min-max;    Woodall";    s Conjecture;    Edmonds-Giles Conjecture;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/1024/1/am2willi2004.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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.