学位论文详细信息
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.
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
Packing Directed Joins | 1755KB | download |