United States of America Us

Logo of the site EPFL Press Logo of the site EPFL Press Logo of the site EPFL Press Logo of the site EPFL Press

Medias

Après une brève introduction aux concepts de base de la théorie des graphes, de la théorie de la complexité et de celle de la combinatoire polyédrique, cet ouvrage se centre sur l'étude de problèmes combinatoires possédant une propriété de 'décomposition', c'est-à-dire tels que chacun d'eux puisse être décomposé en plusieurs sous-problèmes distincts dont les solutions permettent de reconstruire la solution du problème initial. Pour ce type de problèmes, une méthode générale conduisant à une formulation du problème sous forme de programmation linéaire est décrite et appliquée à plusieurs problèmes bien connus de la théorie des graphes (coupe maximum, ensemble stable de poids maximum, arbre de Steiner¬Ö) restreints à des classes de graphes particulières. Un second champ d'application, celui de la composition de polytopes monotones, est ensuite exploré, menant à une généralisation et à l'unification de plusieurs résultats connus, faisant de cet ouvrage une des premières monographiques traitant de composition de polytope de manière détaillée.

  • Introduction et préliminaires
  • Propriété des faces projetées
  • Polytopes associés à des graphes définis par composition
  • Arbres et arborescences sur un 2-arbre
  • Monotonisation de polytopes
  • Composition de systèmes d'indépendants
  • Bibliographie
  • Notations
  • Glossaire.

Publisher: EPFL Press

Author(s): François Margot

Collection: Cahiers mathématiques de l'EPFL

Published: 1 february 1995

Edition: 1st edition

Media: Book

Pages count Book: 184

Format (in mm) Book: 150 x 210

Weight (in grammes): 290 (Book)

Language(s): French

EAN13 Book: 9782880742812

From the same author
In the same collection
People also bought
Related topics
Related to this publication
Available chapters