
Timothé Picavet (doctorant du département CombAlgo, équipe GO) et ses collègues, ont un papier accepté à ICALP’25.
ICALP est la conférence principale et la réunion annuelle de l'Association européenne d'informatique théorique (EATCS), sur les automates, les langages et la programmation. Elle se déroulera en juillet prochain à Aarhus (Danemark).
A cette occasion, l’article de Pierre Aboulker, Édouard Bonnet, Timothé Picavet, et Nicolas Trotignon, intitulé « Induced Disjoint Paths Without an Induced Minor », a été sélectionné.
De quoi s’agit-il ?
Pour relier deux paires de points sans interférence, la modélisation classique consiste à chercher deux chemins disjoints dans le graphe sous-jacent. Ce problème, historique, est parfaitement compris. Nous nous intéressons à une variante récente (qui s'inscrit plus généralement dans la théorie approximative des graphes) : une arête entre les deux chemins crée une interférence, il s'agit de trouver deux chemins non seulement disjoints mais aussi deux à deux non adjacents. Nous montrons que ce problème est significativement plus difficile que ce que la communauté espérait.
En savoir plus sur l’article, ici.