Groupe

GT

Les GT se tiennent chaque vendredi de 14h à 15h (d'ordinaire en salle 178, ils se sont dématérialisés jusqu'à nouvel ordre). Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Voir l'agenda des GT: webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.html https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; pour l'ajouter au vôtre, webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.ics https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics ou bien flasher le QRCode suivant:

Prochains exposés :

Les exposés en ligne sont accessibles à cette adresse : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.

Vendredi 2 décembre à 14h - Cyril Gavoille
Smaller Universal Graphs for Caterpillars and Graphs of Bounded Path-Width, Part 2
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in French, English slides)
In this talk, I will given a rather simple construction of a graph Un with at most 8n vertices with the property that every n-vertex caterpillar is isomorphic to some induced-subgraph of Un. Previous constructions of so-called induced-universal graph for caterpillars used 256n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. FOCS'15).

Then, I will also present an extension to path-width-p graphs with an induced-universal graph of n.2O(p) vertices. This is complemented with a n.2Ω(p) lower bound. With bounded path-width graphs, our construction considerably enlarge the family of n-vertex graphs having an induced-universal graph of O(n) vertices, which is optimal. Such unexpected property was known only for trees, bounded maximum degree outerplanar graphs and maximum degree-2 graphs.

The extended result is obtained from an algorithmic approach by designing an adjacency labeling scheme for these graphs using log(n) + O(p) bit vertex labels and with a constant time adjacency test.

This is a joint work with Arnaud Labourel.

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki