Équipe thématique Pôle Algorithmes et structures discrètes Théorie et algorithmique des graphes Responsable Reza Naserasr Thèmes de recherche Les recherches de l’équipe Théorie et algorithmique des graphes s'articulent autour des propriétés structurelles des graphes, et de la conception d'algorithmes efficaces pour ces structures. L'équipe possède une forte expertise sur les propriétés structurelles de classes de graphes héréditaires. L'hérédité peut être liée à la notion de sous graphe induit aussi bien qu'à la notion de mineur. Une approche frèquente est de chercher pour ces classes de graphes des théorèmes dits de décomposition pour lesquels il est pertinent de savoir calculer de façon efficace de telles décomposition, à la fois pour obtenir des algorithmes de reconnaissance efficace mais aussi pour obtenir pour ces classes des algorithmes polynomiaux pour des des problèmes qui seraient NP-difficiles en toute généralité. Par ailleurs, les problèmes (théoriques ou algorithmiques) liés à la coloration de graphes constituent aussi un domaine d'expertise de notre équipe. Plus récemment, l'équipe s'intéresse aux applications de l'algorithmique à la biologie et la biochimie et aussi à la notion de limite infinie de structures. Les domaines d'applications des travaux de l'équipe ont principalement trait à la conception de protocoles pour les réseaux pair-à-pair, et à l'analyse de différents types de réseaux sociaux (graphe du Web, petits mondes, etc.). Une partie des membres de l'équipe sont à ce titre membres du projet INRIA GANG dont l’objectif est le développement de méthodes algorithmiques pour la conception et le contrôle des réseaux à grande échelle. Séminaire Séminaire algorithmique distribuée et graphes Permanents Nom@TéléphoneBureauFonctionPôleÉquipe Chapuy Guillaume @ 01 57 27 94 04 4012 Directeur.rice de recherche - CNRS ASD combi , graphes Charbit Pierre @ 01 57 27 92 41 4008b Maître.sse de conférences ASD graphes De Montgolfier Fabien @ 01 57 27 92 41 4008b Maître.sse de conférences ASD graphes , distribue Habib Michel @ 01 57 27 94 42 3042a Professeur.e émérite ASD graphes , distribue Mitsou Valia @ 01 57 27 94 45 4034a Maître.sse de conférences ASD graphes Naserasr Reza @ 01 57 27 93 38 4026 Chargé.e de recherche - CNRS ASD graphes Rabie Mikael @ 01 57 27 93 38 4021 Maître.sse de conférences ASD graphes , distribue Ravelomanana Vlady @ 01 57 27 94 44 3025 Professeur.e ASD combi , graphes Stehlik Matej @ 01 57 27 93 36 4008 Professeur.e ASD graphes Viennot Laurent @ 01 57 27 92 50 3016 Directeur.rice de recherche - INRIA ASD graphes , distribue Non-permanents Nom@TéléphoneBureauFonctionPôleÉquipe Agarwala Aryan @ Stagiaire ASD algocomp , graphes Aubian Guillaume @ 4057 Doctorant.e ASD graphes Ben-Dali Houcine @ 4057 Doctorant.e ASD combi , graphes Brunelli Filippo @ 4060 Doctorant.e ASD graphes , distribue Csikos Monika @ 4053 Post-Doctorant.e ASD algocomp , graphes Gujgiczer Anna @ 4008a Visiteur.euse ASD graphes He Jingxiang @ Doctorant.e ASD graphes Nguyen Minh-Hang @ 4031 Doctorant.e ASD graphes , distribue Objois Etienne @ 4059 Stagiaire ASD combi , graphes Pang Xinhong @ Doctorant.e ASD graphes Pujol Cyril @ 3010 Stagiaire ASD graphes Torfs Renaud @ 4059 Doctorant.e ASD graphes Yu Weiqiang @ 4060 Doctorant.e ASD graphes