Ioan Todinca (LIFO - Université d'Orléans)

Les graphes étant des objets complexes, on tente souvent de les “simplifier” si possible sans leur apporter beaucoup de modifications. Une technique courante consiste à rajouter des arêtes au graphe en entrée afin d’obtenir un graphe plus simple.

Une complétion d’intervalles d’un graphe quelconque G est un graphe d’intervalles H , obtenu à partir de G en lui rajoutant des arêtes. On cherche classiquement à minimiser certains paramètres comme le nombre d’arêtes rajoutées ou la taille de la clique de cardinal maximum de H. Ces problèmes étant NP-difficiles, nous nous intéressons aux complétion d’intervalles minimales, où l’on demande simplement à ce que l’ensemble d’arêtes ajoutées soit minimal par inclusion. Je montrerai comment calculer une telle complétion et j’évoquerai des applications au calcul de la largeur linéaire pour des graphes particuliers.