Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Largeur de rang des graphes dénombrables. Définitions et compacité.
du 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