m

F Nous contacter


0
     
Post-edited

H 2 Le problème Graph Motif - Partie 1

Auteurs : Fertin, Guillaume (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...
pattern matching biological networks Graph Motif problem NP-complete problem reduction (NP-hardness proof) fixed-parameter tractability computational complexity

Résumé : 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.

Codes MSC :
05C15 - Coloring of graphs and hypergraphs
05C85 - Graph algorithms
05C90 - Applications of graph theory
68Q17 - Computational difficulty of problems
68Q25 - Analysis of algorithms and problem complexity
68R10 - Graph theory in connection with computer science
92D20 - Protein sequences, DNA sequences
92C42 - Systems biology, networks

Ressources complémentaires :
http://gt-alea.math.cnrs.fr/alea2017/slides/GuillaumeFertinCours-ALEA2017.pdf
http://fpt.wikidot.com/

    Informations sur la Vidéo

    Réalisateur : Hennenfent, Guillaume
    Langue : Français
    Date de publication : 30/03/17
    Date de captation : 22/03/17
    Collection : Research School ; Combinatorics ; Computer Science ; Mathematics in Science and Technology
    Format : MP4 (.mp4) - HD
    Durée : 01:08:53
    Domaine : Computer Science ; Combinatorics ; Mathematics in Science & Technology
    Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctorants , Post - Doctorants
    Download : https://videos.cirm-math.fr/2017-03-22_Fertin_part1.mp4

Informations sur la rencontre

Nom de la rencontre : ALEA Days / Journées ALEA
Organisateurs de la rencontre : Gerin, Lucas ; Pierrot, Adeline ; Gittenberger, Bernhard
Dates : 20/03/17 - 24/03/17
Année de la rencontre : 2017
URL Congrès : http://conferences.cirm-math.fr/1590.html

Citation Data

DOI : 10.24350/CIRM.V.19145503
Cite this video as: Fertin, Guillaume (2017). Le problème Graph Motif - Partie 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19145503
URI : http://dx.doi.org/10.24350/CIRM.V.19145503

Voir aussi

Bibliographie



Z