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:20250330T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20251026T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20250114T104500
DTEND;TZID=Europe/Paris:20250114T114500
DTSTAMP:20260421T171555
CREATED:20250121T094507Z
LAST-MODIFIED:20250121T094507Z
UID:11774-1736851500-1736855100@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Abdallah Saffidine (Univ. South New Wales\, Sydney\, Australie)\, « Generalizing Roberts’ characterization of unit interval graphs? How not to do it! »
DESCRIPTION:A celebrated result by Roberts [1969] establishes that an interval graph can be represented by unit-length intervals on the real line if and only if no vertex has three non-adjacent neighbors. In 2016\, Durán et al. conjectured a generalization of this result\, which we recently investigated. We ran an industrial mixed integer programming (MIP) solver on a cluster for several months\, looking for a counter-example to the conjecture. With no success in sight\, we decided another approach was needed. Going back to the drawing board was surprisingly successful: not only did we prove the conjecture to be true; but we also proved it to be false by exhibiting a counter-example that would have eluded our MIP solver for decades. This talk resolves this apparent inconsistency and can serve as a very gentle introduction to structural graph theory. \nBased on joint work with Virginia Ardévol Martínez\, Romeo Rizzi\, Florian Sikora\, and Stéphane Vialette\, MFCS 2024.
URL:https://www.greyc.fr/event/seminaire-algorithmique-abdallah-saffidine-univ-south-new-wales-sydney-australie-generalizing-roberts-characterization-of-unit-interval-graphs-how-not-to-do-it/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR