Structural and algorithmic aspects of partial orderings of graphs

Jean-Florent Raymond 1, 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Le thème central à cette thèse est l’étude des propriétés des classes de graphes définies par sous-structures interdites et leurs applications. La première direction que nous suivons a trait aux beaux ordres. À l’aide de théorèmes de décomposition dans les classes de graphes interdisant une sous-structure, nous identifions celles qui sont bellement-ordonnées. Les ordres et sous-structures considérés sont ceux associés aux notions de contraction et mineur induit. Ensuite, toujours en considérant des classes de graphes définies par sous-structures interdites, nous obtenons des bornes sur des invariants comme le degré, la largeur arborescente, la tree-cut width et un nouvel invariant généralisant la maille. La troisième direction est l’étude des relations entre les invariants combinatoires liés aux problèmes de packing et de couverture de graphes. Dans cette direction, nous établissons de nouvelles relations entre ces invariants pour certaines classes de graphes. Nous présentons également des applications algorithmiques de ces résultats.
Type de document :
Thèse
Discrete Mathematics [cs.DM]. Université de Montpellier; University of Warsaw, 2016. English
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/tel-01486769
Contributeur : Jean-Florent Raymond <>
Soumis le : vendredi 10 mars 2017 - 13:43:31
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : dimanche 11 juin 2017 - 15:04:47

Fichier

Identifiants

  • HAL Id : tel-01486769, version 1

Collections

Citation

Jean-Florent Raymond. Structural and algorithmic aspects of partial orderings of graphs. Discrete Mathematics [cs.DM]. Université de Montpellier; University of Warsaw, 2016. English. 〈tel-01486769〉

Partager

Métriques

Consultations de la notice

351

Téléchargements de fichiers

201