Chargement Évènements

« Tous les Évènements

  • Cet évènement est passé

Séminaire Algorithmique : Abdallah Saffidine (Univ. South New Wales, Sydney, Australie), « Generalizing Roberts’ characterization of unit interval graphs? How not to do it! »

14 janvier / 10:45 - 11:45

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.

Based on joint work with Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora, and Stéphane Vialette, MFCS 2024.

Détails

Date :
14 janvier
Heure :
10:45 - 11:45
Catégories d’évènement:
, ,
Voir le site évènement

Organisateur

Etienne Grandjean

Lieu

Sciences 3- S3 351