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 , 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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2009, 309, pp.6000-6008. <10.1016/j.disc.2009.04.033>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432698
Contributeur : Stephan Thomasse <>
Soumis le : mardi 31 août 2010 - 15:10:03
Dernière modification le : mercredi 28 septembre 2016 - 15:37:30
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:26:32

Fichier

partsub.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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>

Partager

Métriques

Consultations de
la notice

438

Téléchargements du document

200