Groupe

GT

Seminars are given every Friday from 2:00 to 3:00 (usually in room 178, but not for the time being). You are welcome 10 minutes earlier for tea, coffee and cake.

In order to receive the announcements, just send an email to sympa@diff.u-bordeaux.fr with subject "subscribe labri.go-gt Cookie Monster", where Cookie is your first name and Monster your last name.

See the agenda of the seminars: 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; to add it to yours 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 , or flash the following QRCode:

Next talks:

The online talks are available here : 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.

Jobs

Group

GT Graphs and Optimization

History

 Previous Years

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki