BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:ef06160c-9f25-4af2-a740-c0f7e7afd2f5
X-WR-CALNAME:[gt.go] - 'Smaller Universal Graphs for Caterpillars and Graph
 s of Bounded Path-Width (part 2)' by Cyril Gavoille
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20241027T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20220327T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20230326T020000
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ef06160c-9f25-4af2-a740-c0f7e7afd2f5
DTSTAMP:20260414T215205Z
CLASS:PUBLIC
DESCRIPTION:/Exposé en français/Talk in french / Transparents en anglais/En
 glish slides/ \n\nIn this talk\, I will given a rather simple construction
  of a graph U n with at most 8n vertices with the property that every n-ve
 rtex caterpillar is isomorphic to some induced-subgraph of U n . Previous 
 constructions of so-called induced-universal graph for caterpillars used 2
 56n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. FO
 CS'15). \n\nThen\, I will also present an extension to path-width-p graphs
  with an induced-universal graph of n.2 O(p) vertices. This is complemente
 d with a n.2 Ω(p) lower bound. With bounded path-width graphs\, our \ncons
 truction considerably enlarge the family of n-vertex graphs having an indu
 ced-universal graph of O(n) vertices\, which is optimal. Such unexpected p
 roperty was known only for trees\, bounded maximum degree outerplanar grap
 hs and maximum degree-2 graphs. \n\nThe extended result is obtained from a
 n algorithmic approach by designing an adjacency labeling scheme for these
  graphs using log(n) + O(p) bit vertex labels and with a constant time adj
 acency test. \n\nThis is a joint work with Arnaud Labourel. \n\n[Cyril Gav
 oille] (Université de Bordeaux ) \n\nhttps://dept-info.labri.fr/~gavoille/
  \n\n\nRemarks / Remarques \n\nFind all the information of the working gro
 up on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?u
 serlang=en | web page ] . \nRetrouvez toutes les informations du GT sur ce
 tte [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page w
 eb ] .
DTSTART;TZID=Europe/Paris:20221202T140000
DTEND;TZID=Europe/Paris:20221202T150000
LOCATION:https://webconf.u-bordeaux.fr/b/mar-ef4-zed and LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'Smaller Universal Graphs for Caterpillars and Graphs of 
 Bounded Path-Width (part 2)' by Cyril Gavoille
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
