| Packing Directed Joins (2004) | |||||||||||||||
Abstract | |||||||||||||||
| Edmonds and Giles [4] 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 dual to the Lucchesi-Younger Theorem [10], [9] which proves that the maximum number of directed cuts in a packing is equal to the minimum weight of a directed join, for any weighted directed graph. Schrijver [13], Feofilo# and Younger [5], [6] proved that the conjecture does hold for directed graphs with directed paths from every source to every sink. Schrijver [13] noted that this implies versions of Menger's Theorem, Gupta's Theorem, and Edmonds's Branching Theorem [13]. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||