lipn

Laboratoire d'Informatique de Paris Nord

UMR 7030, Université Paris 13, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse

up13 cnrs

Optimisation dans les Graphes

De nombreux problèmes d'optimisation s'expriment naturellement dans les graphes et hypergraphes. Nous nous attachons ici à en caractériser la complexité et à exploiter la structure de graphe pour proposer des algorithmes de résolution efficaces. Les approches adoptées et les outils que celles-ci invoquent sont riches en diversité : réduction, caractérisation polyédrale, graphes, programmation mathématique, modèles séquentiel ou distribué, etc. De plus, la motivation à aborder un problème spécifique est duale : il peut s'agir de résoudre une question ouverte à propos d'un problème classique (plus grand sous-graphe, partitionnement, couverture, séquencement,...), ou de concevoir les algorithmes « les plus efficaces » pour un problème émergeant d'un domaine d'application ou d'un contexte scientifique donné (transport, conception de réseau, fouille de données, imagerie médicale, ...).

Les résultats obtenus par l'équipe dans ce cadre s'inscrivent dans quatre grandes problématiques :

Nous faisons le choix de ne présenter qu'un petit nombre de problèmes ou problématiques, afin d'illustrer le mieux possible la nature des questions posées et des approches mises en œuvre pour y répondre:

pres

w3c-xhtml