Abstract FR:

On étudie deux nouveaux algorithmes destinés à calculer la force d'un graphe et la partition correspondante par contractions successives. Le premier algorithme procède par ajouts et échanges d'arêtes sur les forêts du graphe. On montre qu'il s'effectue en temps polynomial. Le deuxième algorithme utilise la maximisation de formes linéaires sur le polyèdre convexe associé au graphe. On montre qu'il est polynomial en probabilité.