28967 articles – 22394 Notices  [english version]

lirmm-00432698, version 1

Submodular Partition Functions

Omid Amini () 1, Frédéric Mazoit 2, Nicolas Nisse 3, Stéphan Thomassé () 4

Discrete Mathematics 309 (2009) 6000-6008

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.

  • 1 :  Département de Mathématiques et Applications (DMA)
  • CNRS : UMR8553 – Ecole normale supérieure de Paris - ENS Paris
  • 2 :  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
  • CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
  • 3 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • 4 :  Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
  • CNRS : UMR5506 – Université Montpellier II - Sciences et techniques
  • Domaine : Informatique/Mathématique discrète
 
  • lirmm-00432698, version 1
  • http://hal-lirmm.ccsd.cnrs.fr/lirmm-00432698
  • oai: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 6 Février 2013, 15:32:17