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:20260329T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20261025T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20260303T104500
DTEND;TZID=Europe/Paris:20260303T114500
DTSTAMP:20260406T000313
CREATED:20260302T095103Z
LAST-MODIFIED:20260302T095103Z
UID:12054-1772534700-1772538300@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Packing many dominating sets in a graph »\, François Pirot (LISN\, Univ. Paris-Saclay)
DESCRIPTION:Given a graph G\, a dominating set of G is a subset of vertices S such that every vertex not in S is adjacent to at least one vertex in S; that is\, NG[S] = V(G). While classical studies focus on finding the smallest dominating set of G\, our focus shifts to finding the maximum number of disjoint dominating sets in G\, i.e. its domatic number DOM(G). One can observe that for every graph G of minimum degree d ≥ 1\, 2 ≤ DOM(G) ≤ d + 1\, and both these bounds are tight regardless of the value of d. We are interested\, on the contrary\, in classes of graphs where the above lower bound is not tight\, and to that end introduce the notion of DOM-boundedness. We say that a class of graphs C is DOM-bounded if there exists a function fC → ∞ such that DOM(G) ≥ fC (δ(G)) for every graph G ∈ C\, where δ(G) denotes the minimum degree of G. In that case\, we say that fC is a DOM-binding function of C. \nWe present a probabilistic technique\, relying mainly on the celebrated Lovasz Local Lemma\, to exhibit pseudo-linear DOM-binding functions for several classes of graphs\, such as regular graphs\, unit disk graphs\, and star-free graphs. We also discuss cographs and line graphs\, which turn out to have a linear DOM-binding function. \nJoint work with Quentin Chuet\, Selma Djelloul\, Hoang La\, and Hossein Zaredehabadi.
URL:https://www.greyc.fr/event/seminaire-algorithmique-packing-many-dominating-sets-in-a-graph-francois-pirot-lisn-univ-paris-saclay/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20260324T104500
DTEND;TZID=Europe/Paris:20260324T114500
DTSTAMP:20260406T000313
CREATED:20260302T095221Z
LAST-MODIFIED:20260302T095221Z
UID:12056-1774349100-1774352700@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Mehrdad Nasernejad (GREYC\, Caen)
DESCRIPTION:Résumé à venir.
URL:https://www.greyc.fr/event/seminaire-algorithmique-mehrdad-nasernejad-greyc-caen/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR