Graph Searches with Applications to Cocomparability Graphs

Résumé : Cette thèse propose un modèle général de parcours de graphe à base de tie-break sur des ensembles d'étiquettes. Par ailleurs nous étudions la structure des graphes de cocomparabilité (graphes dont les complémentaires sont ordonnables transitivement). En particulier nous les caractérisons à l'aide de la théorie des treillis des antichaînes maximales. Nous montrons commnt calculer simplement à l'iade de parcours de graphes certaines propriétés des graphes de cocomparabilité. Enfin nous proposons deux nouveaux parcours lexicographiques de graphes LEXUP, LEXDOWN dont nous établissons les premières propriétés.
Type de document :
Thèse
Computer Science [cs]. Université Denis Diderot Paris 7, 2014. English
Liste complète des métadonnées

Littérature citée [51 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01273352
Contributeur : Michel Habib <>
Soumis le : vendredi 12 février 2016 - 12:13:03
Dernière modification le : jeudi 11 janvier 2018 - 06:17:42

Identifiants

  • HAL Id : tel-01273352, version 1

Collections

Citation

Jérémie Dusart. Graph Searches with Applications to Cocomparability Graphs. Computer Science [cs]. Université Denis Diderot Paris 7, 2014. English. 〈tel-01273352〉

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

71