en fr Graph Searches with Applications to Cocomparability Graphs Parcours de graphes et applications aux graphes de cocomparabilité Report as inadecuate




en fr Graph Searches with Applications to Cocomparability Graphs Parcours de graphes et applications aux graphes de cocomparabilité - Download this document for free, or read online. Document in PDF available to download.

1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications

Abstract : This thesis contains a global study on graph searches, introducing a new formal madel to study graph search.But also we study the applications of known graph searches such as LBFS Lexicographic Breadth First Search, LDFS Lexicographic Depth First Search on cocomparability graphs. To this aim we mainly study the maximal antichain lattice of a partial order.Two new graph searches LexUP and LexDown are proposed and their first properties studied.

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.

en fr

Keywords : graph search cocomparability graphs partial orders lattices maximal antichain lattices

Mots-clés : parcours de graphes graphes de cocomparabilité ordres partiels treillis treillis des antichaînes maximales





Author: Jérémie Dusart -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents