en fr Graph Searches with Applications to Cocomparability Graphs Parcours de graphes et applications aux graphes de cocomparabilité Reportar como inadecuado




en fr Graph Searches with Applications to Cocomparability Graphs Parcours de graphes et applications aux graphes de cocomparabilité - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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





Autor: Jérémie Dusart -

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



DESCARGAR PDF




Documentos relacionados