© Alexandra Covaci

Édouard BonnetChargé de recherche CNRS, membre du LIP

Médaille de bronze du CNRS

Chargé de recherche CNRS en théorie des graphes au Laboratoire de l'informatique du parallélisme1 .
 
Édouard Bonnet est algorithmicien, spécialisé dans la théorie des graphes. Champ essentiel de l’informatique, les graphes sont des objets fondamentaux qui permettent de représenter des problèmes très variés issus d’autres disciplines. Il s’est attelé à cette thématique dès sa thèse et a poursuivi avec des post-doctorats en Hongrie, au Royaume-Uni puis à Lyon. Recruté au CNRS en 2018, il étudie aujourd’hui les solutions les plus efficaces possibles pour les problèmes algorithmiques posés sous forme de graphes. Pour pouvoir les utiliser ou les comparer, il est souvent nécessaire de les décomposer en des éléments plus simples. En 2020, Édouard Bonnet et son équipe inventent la notion de « twin-width », méthode basée sur un processus dynamique de contraction, où l’on fusionne successivement deux sommets du graphe en un seul. Cette nouvelle approche de décomposition pourrait faciliter la résolution de différents problèmes du domaine : les problèmes polynomiaux, comme trouver le plus court chemin entre deux points d’un réseau ; et les problèmes combinatoires exponentiels, comme dessiner le plus court chemin passant par tous les sommets du graphe.

  • 1CNRS/ENS de Lyon/Université Claude Bernard Lyon 1

En savoir plus

Édouard Bonnet médaillé de bronze du CNRS pour ses travaux sur les graphes : actualité publiée à l'occasion de la remise de la médaille de bronze du CNRS (03/04/2023)

ANR Twin-width : un projet pour mieux décomposer des graphes : actualité publiée au sujet d'un projet ANR (05/07/2022) 

Analyse multivariée d’algorithmes : au-delà des problèmes NP-difficiles : actualité publiée à l'occasion des 30 ans du Laboratoire de l'informatique du parallélisme (LIP - CNRS/ENS de Lyon/Université Claude Bernard Lyon 1) (21/12/2018)