ALEA Days / Journées ALEA

Collection ALEA Days / Journées ALEA

Organizer(s) Elvey Price, Andrew ; Lecouvey, Cédric ; Mailler, Cécile ; Raschel, Kilian
Date(s) 13/03/2023 - 15/03/2023
linked URL https://conferences.cirm-math.fr/2887.html
00:00:00 / 00:00:00
11 34

Le problème Graph Motif - Partie 1

By Guillaume Fertin

Also appears in collection : Ecoles de recherche

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que (1) le multi-ensemble des couleurs de V' correspond à M, (2) le sous-graphe G' induit par V' est connexe. Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique. Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique. Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.19145503
  • Cite this video Fertin, Guillaume (22/03/2017). Le problème Graph Motif - Partie 1. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19145503
  • URL https://dx.doi.org/10.24350/CIRM.V.19145503

Bibliography

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback