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 metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432698
Contributor : Stephan Thomasse <>
Submitted on : Tuesday, August 31, 2010 - 3:10:03 PM
Last modification on : Tuesday, April 2, 2019 - 2:16:09 PM
Long-term archiving on : Wednesday, December 1, 2010 - 2:26:32 AM

File

partsub.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

754

Files downloads

309