Certains résultats de l'équipe [5, 19] utilisent des résultats concernant la théorie des couplages, d'autres (communs avec les classiques des multiflots comme A. Frank, A. Karzanov, M. Lomonosov, visiteurs fréquents à Grenoble), reprennent la théorie russe et l'intègrent dans une des directions de l'optimisation combinatoire. Ainsi, l'article [9] traite un théorème classique à l'aide de la théorie des fonctions sous-modulaires, une méthode qui a conduit nos visiteurs à développer dans [13] le théorème le plus fort dans cette direction de multiflots entiers.
D'autres articles traitent les problèmes de flot sous des contraintes particulières. Dans [3] Bienia et Letrouit développent un algorithme pour les " flots avec sécurité ". L'article [4] est un résultat sur les flots à part dont la méthode devrait subir de nouvelles analyses dans le futur : un théorème sur les flots nulle part zéro est démontré à l'aide d'un problème intéressant de théorie de nombres. Ce problème a eu des succès " médiatiques " grâce à une formulation amusante, et aussi la particularité des méthodes mathématiques.
Après le travail de Seymour qui caractérise les cas quand la condition la plus simple, la " condition des coupes " est nécessaire pour l'existence d'un multiflot, la question du prochain " étage " de conditions s'est posée. Les travaux [14, 16] répondent en partie aux questions posées par A. Sebö dans des travaux précédents : le prochain " étage " de conditions est défini et la classe des matroïdes dans lesquels ces conditions sont nécessaires et suffisantes est caractérisée.
D'autres résultats, au contraire, traitent les coupes ou multicoupes en soi : M. Burlet, Goldschmidt [20] améliorent la complexité du problème des 3-coupes en utilisant des résultats de structure de Karzanov, Lomonosov et Dinitz. Les résultats partiels de M. Burlet et A. Sebö traitent les k-coupes minimum à l'aide de l'algorithme glouton. L'article [1] montre une application du " cut-width " en physique, et donne une démonstration simple à un théorème connu.
Applications des résultats des méthodes combinatoires aux problèmes :
du trafic aérien ;
du trafic routier ;
de la gestion et de l'organisation.
En collaboration avec le LICIT (laboratoire d'Ingénierie Circulation Transports de l'INRETS) nous nous intéressons aux aspects théoriques des problèmes liés aux transports routier et aérien. L'analyse de ces problèmes nous a permis de trouver le lien avec de nombreux modèles d'optimisation combinatoires comme multiflots, flot avec sécurité [3], coloration des graphes d'intersection de segments, multicoupes, k-coupes de poids maximum, minimisation de nombres de " vias " dans un graphe, graphes planaires maximum, décomposition d'un graphe en un nombre minimum de graphes planaires. Pour tous ces problèmes nous cherchons, entre autres, à développer des algorithmes d'approximation et des heuristiques efficaces. Une autre application, en physique est publiée dans [1].