moteur de recherche

Séminaire Algo - Cyril Gavoille
Séminaire Algo - Cyril Gavoille
16-Nov-2021 14:00
Age: 16 days





Cyril Gavoille

Graphe universel et représentation implicite pour les graphes planaires

Salle de séminaire 4B125, bâtiment Copernic

Résumé: Le nombre de graphes planaires à n sommets (non-isomorphes, non étiquetés) est de l'ordre de c(n+o(n)), où c=O(1). Quel est le plus petit graphe qui les contient tous comme sous-graphes induits ? Nous montrons ici qu'il suffit de n(1+o(1)) sommets. Ce résultat, de toute évidence optimal asymptotiquement, repose sur des avancées majeures en théorie structurelle des graphes, dont nous discuterons également.








<- Back to: Accueil