Evènement pour le groupe GT Graphes et Applications


Date 2014-04-18  14:00-15:00
TitreLargeur de rang des graphes dénombrables. Définitions et compacité. 
RésuméLa largeur de rang d'un graphe G, notée rwd(G), (en anglais rank-width) a été introduite par Oum et Seymour dans un but algorithmique, notamment la construction d'algorithmes FPT. On peut souhaiter étendre cette notion aux graphes infinis, et viser la "compacité" : rwd(G) = borne supérieure des rwd(H) pour H sous graphe induit fini de G. La définition la plus naturelle donne "seulement" que la largeur est au plus 2 fois la borne supérieure considérée ci-dessus. En utilisant une notion d'arbre différente (quasi-arbre), qui autorise une infinité de noeuds sur le chemin entre 2 noeuds, on obtient la compacité exacte. Cette notion est définie en logique du premier ordre. On regardera aussi dans cette perspective la largeur de rang linéaire, où l'arbre de décomposition est un ordre total sur les sommets du graphe.  
LieuSalle 178 
OrateurBruno Courcelle 



Aucun document lié à cet événement.

Retour
Retour à l'index