Bonat, Dr. Thorsten

Le problème de coupe maximale est un problème d'optimisation combinatoire NP-difficile défini sur des graphes pondérés non orientés. Elle consiste à trouver un sous-ensemble des nœuds du graphe tel que le poids agrégé des arêtes entre le sous-ensemble et son complémentaire soit maximisé. Ce livre traite d'une nouvelle approche de séparation à utiliser dans un algorithme de branchement et de coupe pour résoudre les problèmes de coupe maximale jusqu'à l'optimalité. La méthode est basée sur la contraction des graphes et...