Skip to Main content Skip to Navigation
Journal articles

Submodular Partition Functions

Omid Amini 1 Frédéric Mazoit 2 Nicolas Nisse 3 Stéphan Thomassé 4
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Stephan Thomasse Connect in order to contact the contributor
Submitted on : Tuesday, August 31, 2010 - 3:10:03 PM
Last modification on : Friday, October 15, 2021 - 1:37:11 PM
Long-term archiving on: : Wednesday, December 1, 2010 - 2:26:32 AM


Files produced by the author(s)



Omid Amini, Frédéric Mazoit, Nicolas Nisse, Stéphan Thomassé. Submodular Partition Functions. Discrete Mathematics, Elsevier, 2009, 309, pp.6000-6008. ⟨10.1016/j.disc.2009.04.033⟩. ⟨lirmm-00432698⟩



Record views


Files downloads