Corte mínimo Flujo máximo - Encontrar el corte con menos vértices

Question

Supongamos que una red $N = (G,c,s,t)$ donde $c$ es real.

¿Cómo se encuentran todos los minicortes? (o cómo encontrar el corte con el menor número de vértices)

He intentado trastear con la capacidad, pero como puede ser real no consigo que funcione.

EDIT: Intentaré reformular la pregunta más claramente : Entre todos los $(S,T)$ recorta en $G$ que tienen una capacidad mínima, encontrar el que tiene el menor número de vértices.

(O, de forma parecida, cómo encontrar todos los min $(S,T)$ recorta en $G$ ? )

Answer 1

El número de particiones A,B que inducen un corte mínimo es como máximo $n^2$ y se pueden enumerar en el tiempo $O(n^2 \log^3 n)$ utilizando el algoritmo de contracción recursiva de Karger y Stein. Por lo tanto, es una cuestión sencilla determinar cualquier propiedad que desee de los cortes mínimos.