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é:   
Sur la dimension cubique de quelques classes d'arbres
du groupe GT Graphes et Applications

Date 2010-11-26  14:00-15:00
TitreSur la dimension cubique de quelques classes d'arbres 
RésuméRésumé : Arffati, Papadimitriou et Papageorgiou ont montré que le problème de décider si un graphe G est plongeable dans un hypercube de dimension donnée est NP-complet. Corneil et Wagner ont montré que ce problème reste NP-complet même dans le cas où G est un arbre. Plusieurs auteurs se sont intéressés à l’étude de plongement d’arbres dans l’hypercube ce qui a permis de caractériser certaines classes. Tous les arbres sont plongeables dans l’hypercube, le problème consiste à donner la plus petite dimension d’un hypercube dans lequel un arbre donné est plongeable. On parle alors d’hypercube optimal et de la dimension cubique de l’arbre. De nombreux problèmes (booléens, de théorie des graphes, de codes…) sont formalisables comme problèmes combinatoires sur l’hypercube, donc il est fondamental de déterminer quels sont les graphes et particulièrement les arbres qui sont plongeables dans l’hypercube et de déterminer aussi combien de copies d’un arbre donné on peut placer (de façon disjointe) dans un hypercube de dimension donnée. Nous avons introduit quelques classes d’arbres pour lesquelles nous avons déterminé la dimension cubique et nous avons aussi donné pour certaines classes le nombre maximum de copies que l’on peut placer dans un hypercube de dimension donnée. Un problème d’une autre nature a été traité, il concerne la détermination du nombre de sommets minimum et du nombre de sommets maximum d’une famille de graphes plongeables dans un même hypercube optimal. Mots-clés : Hypercube, Plongement, Graphe, Arbre, Isomorphisme.  
LieuSalle 76 
OrateurKamal Kabyl 



Aucun document lié à cet événement.

Retour
Retour à l'index