 |
HAL-LIRMM - Open Archive |  |
Journal articles
Submodular Partition Functions
Abstract : Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble number of a graph and its tree-width. Our approach is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The proof does not rely on Menger's theorem, and thus generalises the original one. It thus provides a dual for matroid tree-width. One can also derive all known dual notions of other classical width-parameters from it.
Cited literature [6 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432698
Contributor : Stephan Thomasse <>
Submitted on : Tuesday, August 31, 2010 - 3:10:03 PM
Last modification on : Monday, November 9, 2020 - 3:32:34 PM
Long-term archiving on: : Wednesday, December 1, 2010 - 2:26:32 AM
Contributor : Stephan Thomasse <>
Submitted on : Tuesday, August 31, 2010 - 3:10:03 PM
Last modification on : Monday, November 9, 2020 - 3:32:34 PM
Long-term archiving on: : Wednesday, December 1, 2010 - 2:26:32 AM
File
partsub.pdf
Files produced by the author(s)