BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230321T100000
DTEND;TZID=Europe/Paris:20230321T110000
DTSTAMP:20260423T135648
CREATED:20230213T105826Z
LAST-MODIFIED:20230310T144055Z
UID:11100-1679392800-1679396400@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Martin Pépin (LIPN\, Univ. Paris Nord) « Directed Ordered Acyclic Graphs\, asymptotic analysis and efficient random sampling »
DESCRIPTION:Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70’s by Robinson. \nIn this talk\, I will introduce a new class of DAGs (DOAGs for Directed Ordered Acyclic Graphs)\, endowed with an independent ordering of the children of each vertex. They offer a new modelisation tool for objects arising from the compaction of tree-like structures. \nFor this class we obtain a recursive decomposition scheme that is amenable to effective random sampling with control over the number of edges\, an optimised sampler for the case when the number of edges is free\, and prove an unusual asymptotic behaviour. I will also show that our approach also applies to classical DAGs\, thus providing a solution to the problem of sampling DAGs with a prescribed number of edges.
URL:https://www.greyc.fr/event/seminaire-algorithmique-martin-pepin-lipn-univ-paris-nord/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR