Submodular Partition Functions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2009

Submodular Partition Functions

Résumé

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.
Fichier principal
Vignette du fichier
partsub.pdf (172.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00432698 , version 1 (31-08-2010)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More