Corte mínimo

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué es un corte

Un corte divide los vértices de un grafo en dos grupos no vacíos, S y el resto, V \ S. Las aristas con un extremo en cada grupo cruzan el corte, y al eliminarlas los dos grupos quedan desconectados entre sí. En un grafo ponderado, el peso de un corte, también llamado su capacidad, es el peso total de las aristas que lo cruzan; en un grafo sin pesos es simplemente su número. Un corte mínimo es un corte de peso mínimo: la forma más barata de romper el grafo en dos partes.

El ejemplo que nos acompaña es una pequeña red informática de 8 routers unidos por 15 enlaces. Cada peso es la capacidad de un enlace en gigabits por segundo. Los routers A a D están en un edificio y E a H en otro:

edificio 1:  A-B 4   A-C 3   A-D 2   B-C 2   B-D 3   C-D 3
edificio 2:  E-F 3   E-G 2   E-H 3   F-G 4   F-H 2   G-H 3
entre ambos: C-E 2   D-F 1   B-G 1

8 routers, 15 enlaces, capacidad total 38

Cortar los tres enlaces entre los edificios, C-E, D-F y B-G, cuesta 2 + 1 + 1 = 4 y divide la red en dos. Ese es el corte mínimo, y es el único corte de peso 4. También es el punto más débil de la red: el máximo tráfico que pueden intercambiar los dos edificios es de 4 gigabits por segundo, se configure como se configure el resto de la red. El siguiente corte más barato aísla el router H, con un coste de 8, la suma de sus propios enlaces.

2. Dos problemas con el mismo nombre

"Corte mínimo" designa dos problemas relacionados, y la mayor parte de la confusión sobre el tema viene de mezclarlos:

• Corte mínimo s-t. Se dan dos vértices, una fuente s y un sumidero t, y el corte debe separarlos: s en S, t fuera. Este es el corte del teorema de flujo máximo y corte mínimo de la sección 4. En el ejemplo, el corte mínimo que separa A de H es el corte entre edificios, de peso 4, pero el corte mínimo que separa A de B tiene peso 9: como ambos están en el mismo edificio, la opción más barata es aislar A por sí solo.
• Corte mínimo global. No se da ningún vértice; el corte puede separar dos grupos cualesquiera. Su peso es el menor de todos los cortes mínimos s-t, y en un grafo sin pesos es igual a la conectividad de aristas λ(G), el menor número de aristas cuya eliminación desconecta el grafo. Las secciones 5 a 7 lo calculan.

Una cota sencilla relaciona las dos ideas. Aislar un solo vértice cuesta la suma de los pesos de sus enlaces, su grado ponderado, así que el corte mínimo global nunca puede superar el grado mínimo. Hassler Whitney demostró la versión sin pesos en 1932: conectividad de vértices ≤ conectividad de aristas ≤ grado mínimo. En el ejemplo, el menor grado ponderado es 8, en H, y el corte mínimo de 4 está muy por debajo: el punto débil es un haz de enlaces entre dos grupos, no un único router mal conectado. Sin los pesos, la cota es ajustada aquí: cada router tiene al menos 3 enlaces, y 3 enlaces son el mínimo necesario para desconectar la red.

3. Por qué probar todos los cortes no escala

Un grafo con n vértices tiene 2n-1 - 1 cortes: cada vértice distinto de un primer vértice fijo va a uno u otro lado, y la división con todo en un mismo lado no es un corte. El ejemplo tiene 27 - 1 = 127, suficientemente pocos para enumerarlos.

from itertools import combinations

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def cut_weight(side, links):
    """Peso total de los enlaces con exactamente un extremo en side."""
    return sum(w for u, v, w in links if (u in side) != (v in side))

def all_cuts(links):
    """Todas las divisiones de los vértices en dos lados no vacíos, cada una contada una vez."""
    vertices = sorted({x for u, v, _ in links for x in (u, v)})
    first, rest = vertices[0], vertices[1:]
    for r in range(len(rest)):                 # side siempre contiene el primer vértice
        for others in combinations(rest, r):
            side = {first, *others}
            yield cut_weight(side, links), ''.join(sorted(side))

cuts = sorted(all_cuts(LINKS))
print(len(cuts), 'cuts')
# 127 cuts
for weight, side in cuts[:4]:
    print(weight, side)
# 4 ABCD
# 8 ABCDEFG
# 9 A
# 9 ABCEFGH

El número se duplica con cada vértice: 50 vértices ya dan más de 560 billones de cortes. El resto de esta guía trata de algoritmos que encuentran el mínimo sin mirar la mayoría de ellos. La guía sobre la complejidad de los algoritmos de grafos explica por qué un crecimiento exponencial como este descarta la fuerza bruta.

4. Cortes mínimos s-t a partir del flujo máximo

El teorema de flujo máximo y corte mínimo, enunciado por Lester Ford y Delbert Fulkerson en un informe de la RAND de 1954 y publicado en 1956, el mismo año en que Peter Elias, Amiel Feinstein y Claude Shannon dieron una demostración distinta, dice que el mayor flujo que se puede enviar de s a t es igual al peso del menor corte que los separa. Una dirección es fácil: cada unidad de flujo tiene que cruzar todos los cortes s-t, así que ningún flujo puede superar ningún corte. El contenido del teorema es que los dos siempre coinciden. La guía sobre el flujo en redes y el teorema de flujo máximo y corte mínimo lo demuestra con caminos de aumento.

La pregunta tuvo un origen militar. En 1955, T. E. Harris y F. S. Ross, de la RAND Corporation, modelaron los ferrocarriles del oeste de la Unión Soviética y de Europa del Este como una red de 44 vértices y 105 aristas, para encontrar el conjunto de líneas más barato de interrumpir. Les interesaba más el corte que el flujo: su informe señala un corte mínimo de 163.000 toneladas como "el cuello de botella". No se desclasificó hasta 1999.

Para calcular cortes, lo importante es cómo se obtiene el corte a partir de un flujo máximo. Cuando ya no queda ningún camino de aumento de s a t, reúne todos los vértices que s todavía puede alcanzar a través de las aristas con capacidad sobrante, que forman el grafo residual. Ese conjunto es el lado S de un corte mínimo, y las aristas saturadas que salen de él forman el corte. El programa de abajo ejecuta el algoritmo de Edmonds-Karp, que siempre aumenta a lo largo de un camino más corto, y después lee el corte. Cada enlace no dirigido puede llevar flujo en cualquiera de las dos direcciones.

from collections import deque

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def min_st_cut(links, s, t):
    """Flujo máximo de Edmonds-Karp y después el corte mínimo s-t leído en el grafo residual."""
    cap = {}
    for u, v, w in links:                      # un enlace no dirigido lleva flujo en ambos sentidos
        cap.setdefault(u, {})[v] = cap.get(u, {}).get(v, 0) + w
        cap.setdefault(v, {})[u] = cap.get(v, {}).get(u, 0) + w
    flow = 0
    while True:
        parent, queue = {s: None}, deque([s])
        while queue and t not in parent:       # camino de aumento más corto por BFS
            u = queue.popleft()
            for v, c in cap[u].items():
                if c > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if t not in parent:
            break
        path, v = [], t
        while parent[v] is not None:
            path.append((parent[v], v))
            v = parent[v]
        push = min(cap[u][v] for u, v in path)
        for u, v in path:                      # gasta capacidad, abre el sentido inverso
            cap[u][v] -= push
            cap[v][u] += push
        flow += push
    side = set(parent)                         # todavía alcanzable desde s en el grafo residual
    cut = [(u, v, w) for u, v, w in links if (u in side) != (v in side)]
    return flow, ''.join(sorted(side)), cut

print(min_st_cut(LINKS, 'A', 'H'))
# (4, 'ABCD', [('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)])
print(min_st_cut(LINKS, 'A', 'B'))
# (9, 'A', [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2)])

De A a H el flujo máximo es 4, y puede dividirse en tres caminos que llevan 2, 1 y 1 unidades. Después, los tres enlaces entre los edificios están saturados, A todavía puede alcanzar B, C y D pero nada más allá, y el corte es exactamente el corte entre edificios. De A a B el flujo es 9 y el corte aísla A. Edmonds-Karp se ejecuta en O(V E2) pasos; existen algoritmos de flujo más rápidos, pero cualquiera que sea correcto da de esta forma un corte mínimo s-t.

Para grafos sin pesos, el teorema tiene una famosa forma combinatoria, que suele llevar el nombre de Karl Menger, cuyo teorema de 1927 es la versión para vértices: el mayor número de caminos de u a v que no comparten ninguna arista es igual al menor número de aristas cuya eliminación separa u de v. Esta forma para aristas del teorema de Menger se deduce del teorema de flujo máximo y corte mínimo. En el ejemplo, ignorando los pesos, hay tres caminos sin aristas en común de A a H, y tres enlaces entre los edificios.

5. Cortes mínimos globales con flujos máximos

Un corte mínimo global separa algún par de vértices, así que es el menor corte s-t sobre todos los pares. Basta con menos pares. Fija cualquier vértice s: sea cual sea el corte mínimo, algún vértice t queda al otro lado, así que el mínimo sobre las n - 1 elecciones de t lo encuentra. En el ejemplo, fijando s = A, las cuatro ejecuciones con t en el otro edificio devuelven todas 4.

Ralph Gomory y T. C. Hu demostraron en 1961 que n - 1 flujos máximos revelan mucho más: construyen un árbol sobre los mismos vértices, que hoy se llama árbol de Gomory-Hu, en el que el corte mínimo entre dos vértices cualesquiera es igual al menor peso de arista en el camino del árbol que los une. Para el ejemplo, las siete aristas del árbol tienen los valores 4, 8, 9, 9, 10, 10 y 10, así que el valor de cada uno de los 28 cortes mínimos entre pares se puede leer en él, y la arista más pequeña, 4, es el corte mínimo global.

Los métodos basados en flujos también funcionan para grafos dirigidos, y son la herramienta adecuada cuando importa el corte mínimo entre vértices concretos. Para el corte mínimo global de un grafo no dirigido, los dos algoritmos siguientes son más sencillos y más rápidos.

6. El algoritmo de Stoer-Wagner

En 1997, Mechthild Stoer y Frank Wagner publicaron un algoritmo que encuentra el corte mínimo global de un grafo no dirigido con pesos no negativos sin usar ningún flujo, a partir de trabajos anteriores de Hiroshi Nagamochi y Toshihide Ibaraki. Se ejecuta en n - 1 fases. Cada fase hace tres cosas:

1. Empezando desde cualquier vértice, añade vértices de uno en uno, eligiendo siempre el más fuertemente conectado a los ya añadidos: el de mayor peso total de enlaces hacia el conjunto que crece. Este orden se conoce como búsqueda de máxima adyacencia.
2. Cuando se añade el último vértice t, el peso de sus enlaces con todo lo demás es el corte de la fase. Un breve argumento muestra que es un corte mínimo que separa t de s, el vértice añadido justo antes.
3. Fusiona s y t en un solo vértice, sumando los pesos de los enlaces paralelos, y empieza la fase siguiente sobre el grafo más pequeño.

O bien el corte mínimo global separa s de t, y en ese caso esta fase lo ha encontrado, o bien los mantiene en el mismo lado, y en ese caso fusionarlos no pierde nada. Tras n - 1 fases, el menor corte de la fase es la respuesta.

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def stoer_wagner(links):
    """Corte mínimo global: n - 1 fases, cada una termina en un corte de la fase y una fusión."""
    w = {}
    for u, v, c in links:
        w.setdefault(u, {})[v] = w.get(u, {}).get(v, 0) + c
        w.setdefault(v, {})[u] = w.get(v, {}).get(u, 0) + c
    groups = {v: v for v in w}                 # los vértices fusionados recuerdan lo que contienen
    best, phase = (float('inf'), ''), 0
    while len(w) > 1:
        phase += 1
        start = min(w)
        order, attached = [start], {v: w[start].get(v, 0) for v in w if v != start}
        while attached:                        # añade a continuación el vértice más fuertemente conectado
            v = max(sorted(attached), key=attached.get)
            phase_cut = attached.pop(v)
            order.append(v)
            for x, c in w[v].items():
                if x in attached:
                    attached[x] += c
        s, t = order[-2], order[-1]
        side = ''.join(sorted(groups[t]))
        print(f'phase {phase}: cut of the phase {phase_cut:2}, side {side}')
        best = min(best, (phase_cut, side))
        for x, c in w.pop(t).items():          # fusiona t en s
            if x != s:
                w[s][x] = w[s].get(x, 0) + c
                w[x][s] = w[x].get(s, 0) + c
            del w[x][t]
        groups[s] += groups.pop(t)
    return best

print(stoer_wagner(LINKS))
# phase 1: cut of the phase  8, side H
# phase 2: cut of the phase 10, side F
# phase 3: cut of the phase 10, side FGH
# phase 4: cut of the phase  4, side EFGH
# phase 5: cut of the phase 10, side C
# phase 6: cut of the phase 10, side B
# phase 7: cut of the phase  9, side BCDEFGH
# (4, 'EFGH')

En el ejemplo, la primera fase termina en H con un corte de 8, el coste de aislarlo. A medida que las fases fusionan vértices, los grupos crecen: en la fase 4, el último vértice añadido es el grupo fusionado E, F, G, H, y su corte de la fase es el corte entre edificios, 4. Las fases restantes solo encuentran cortes mayores. Con un montículo de Fibonacci para la elección del "más fuertemente conectado", cada fase tarda O(E + V log V) y el algoritmo completo O(V E + V2 log V); la versión sencilla de arriba, que recorre los vértices buscando el máximo, tarda O(V3).

7. La contracción aleatoria de Karger

El algoritmo de David Karger de 1993 es uno de los algoritmos aleatorizados más famosos. Es casi demasiado sencillo para funcionar:

1. Elige un enlace al azar, con probabilidad proporcional a su peso, y contráelo uniendo sus dos extremos en un solo vértice y descartando los enlaces entre ellos.
2. Repite hasta que solo queden dos vértices fusionados.
3. Los enlaces entre esos dos vértices forman un corte. Devuélvelo.

Una ejecución puede fallar fácilmente: si en algún momento contrae un enlace del corte mínimo, ese corte se pierde. La sorpresa es que falla lo bastante pocas veces. Un corte mínimo es ligero, así que las elecciones aleatorias tienden a evitar sus enlaces, y Karger demostró que una sola ejecución devuelve un corte mínimo dado con una probabilidad de al menos 2 / (n (n - 1)). Repetir la ejecución y quedarse con el corte más ligero reduce la probabilidad de fallo tan rápido como quieras.

import math, random

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def contract(links, rnd):
    """Una ejecución del algoritmo de Karger: fusiona los extremos de enlaces aleatorios hasta que quedan dos grupos."""
    group = {x: x for u, v, _ in links for x in (u, v)}
    def find(x):
        while group[x] != x:
            x = group[x]
        return x
    groups = len(group)
    while groups > 2:
        alive = [(u, v, w) for u, v, w in links if find(u) != find(v)]
        u, v, _ = rnd.choices(alive, weights=[w for *_, w in alive])[0]   # los enlaces más pesados se fusionan más a menudo
        group[find(u)] = find(v)
        groups -= 1
    side = ''.join(sorted(x for x in group if find(x) == find('A')))
    return sum(w for u, v, w in links if find(u) != find(v)), side

rnd = random.Random(2026)
runs = [contract(LINKS, rnd) for _ in range(10_000)]
hits = sum(weight == 4 for weight, _ in runs)
print(f'minimum cut found in {hits} of 10,000 runs')
print(f'guaranteed at least 2 / (n (n - 1)) = {2 / (8 * 7):.4f} per run')
best_of_10 = [min(runs[i:i + 10]) for i in range(0, 10_000, 10)]
print(f'best of 10 runs is the minimum cut {sum(c[0] == 4 for c in best_of_10)} times out of 1,000')
print(f'runs needed for 99% with only the guarantee: {math.ceil(math.log(100) / -math.log(1 - 2 / 56))}')
# minimum cut found in 3228 of 10,000 runs
# guaranteed at least 2 / (n (n - 1)) = 0.0357 per run
# best of 10 runs is the minimum cut 978 times out of 1,000
# runs needed for 99% with only the guarantee: 127

En 10.000 ejecuciones sobre el ejemplo, el corte mínimo salió 3228 veces, alrededor del 32 %, nueve veces el 3,6 % garantizado. Quedarse con la mejor de 10 ejecuciones lo encontró en 978 de 1000 intentos. La garantía es un peor caso: confiando solo en ella, harían falta 127 ejecuciones para tener un 99 % de confianza con 8 vértices. La cota de Karger tiene además una consecuencia llamativa. Cada corte mínimo se encuentra con una probabilidad de al menos 2 / (n (n - 1)), y estos sucesos no pueden ocurrir a la vez, así que un grafo puede tener como máximo n (n - 1) / 2 cortes mínimos. Un ciclo con n vértices tiene exactamente esa cantidad: eliminar dos cualesquiera de sus aristas es un corte mínimo.

David Karger y Clifford Stein mejoraron el método en 1996 contrayendo solo una parte del camino y después aplicando recursión sobre dos copias, lo que encuentra un corte mínimo con alta probabilidad en O(n2 log3 n) pasos. Karger dio más tarde un algoritmo que se ejecuta en tiempo cuasilineal en el número de aristas.

8. Qué algoritmo usar

En la práctica: para el corte entre dos vértices dados, ejecuta un flujo máximo. Para el corte mínimo global de un grafo no dirigido, Stoer-Wagner es la elección determinista estándar y es lo que implementan bibliotecas como NetworkX. El algoritmo de Karger es al que recurrir cuando el grafo es grande, cuando el cálculo puede repartirse entre muchas máquinas o cuando necesitas todos los cortes mínimos en lugar de uno.

9. Grafos dirigidos y cortes de vértices

En un grafo dirigido, un corte (S, V \ S) cuenta solo los arcos que van de S al otro lado; los arcos que vuelven no ayudan a desconectarlo. Stoer-Wagner y el algoritmo de Karger se basan en la simetría y no se aplican. El corte mínimo global todavía puede encontrarse con flujos máximos, desde un vértice fijo hacia todos los demás y de vuelta, y Jianxiu Hao y James Orlin mostraron en 1994 cómo hacerlo en aproximadamente el tiempo de un solo cálculo de flujo.

A veces la pregunta es qué vértices eliminar en lugar de qué aristas: los routers cuyo fallo dividiría la red. El menor conjunto de este tipo da la conectividad de vértices, y un truco estándar la reduce a cortes de aristas, dividiendo cada vértice en una copia de "entrada" y otra de "salida" unidas por una arista de capacidad 1. Un único vértice cuya eliminación desconecta el grafo es un punto de articulación, y una única arista que lo hace es un puente. Ambos pueden encontrarse en tiempo lineal sin flujos; la guía sobre componentes conexas, puentes y puntos de articulación lo explica.

10. Dónde se usan los cortes mínimos

• Fiabilidad de redes. El corte mínimo global de una red de comunicaciones o eléctrica es su punto más débil: el menor número de enlaces, o la menor capacidad, cuyo fallo la divide. El corte mínimo s-t es el cuello de botella entre dos sitios, como en el ejemplo.
• Segmentación de imágenes. Convierte cada píxel en un vértice unido a sus vecinos, con enlaces pesados entre píxeles parecidos, y añade una fuente para "objeto" y un sumidero para "fondo". Un corte mínimo s-t separa el objeto del fondo a lo largo de la frontera que corta los enlaces más débiles. D. M. Greig, B. T. Porteous y A. H. Seheult usaron por primera vez cortes mínimos en el análisis de imágenes en 1989, para restaurar imágenes binarias con ruido, Zhenyu Wu y Richard Leahy los aplicaron a la segmentación en 1993, y los cortes de grafos interactivos de Yuri Boykov convirtieron el método en una herramienta estándar de la visión por computador.
• Agrupamiento. Un corte mínimo divide un grafo de similitud por donde es más débil. Por sí solo tiende a recortar unos pocos puntos poco conectados, y por eso Jianbo Shi y Jitendra Malik introdujeron el corte normalizado, que divide el peso del corte entre el tamaño de cada lado.
• Selección de proyectos. Elegir proyectos que dan dinero pero requieren prerrequisitos costosos es un problema de corte mínimo disfrazado: los proyectos rentables cuelgan de la fuente, los costes del sumidero, y los prerrequisitos se convierten en arcos de capacidad infinita. La guía de presupuestación de capital resuelve así una cartera de este tipo.
• Eliminación deportiva. Si un equipo todavía puede terminar primero, dados los partidos que quedan, es una cuestión de flujo máximo, y el corte mínimo certifica un "no", como mostró Benjamin Schwartz para el béisbol en 1966.

El problema opuesto, el corte máximo, que busca la división con tantas aristas cruzadas como sea posible, parece similar pero es NP-difícil. Minimizar un corte es fácil porque es dual de un flujo; maximizarlo no tiene esa estructura.

11. Avances recientes

Los cortes mínimos han protagonizado algunos de los avances recientes más llamativos en algoritmia. En 2015, Ken-ichi Kawarabayashi y Mikkel Thorup encontraron un algoritmo determinista para el corte mínimo global de un grafo simple sin pesos que se ejecuta en tiempo cuasilineal. En 2021, Jason Li extendió el tiempo determinista casi lineal a los grafos ponderados. Y en 2022, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg y Sushant Sachdeva demostraron que el flujo máximo con capacidades enteras, y con él el corte mínimo s-t, puede calcularse en tiempo casi lineal m1 + o(1), un resultado que ganó el premio al mejor artículo en FOCS 2022. Estos algoritmos todavía no son los que usa el software práctico, pero establecen a qué velocidad pueden resolverse los problemas en principio.

12. Errores comunes

13. Glosario

15. Referencias

Los teoremas, algoritmos y atribuciones anteriores proceden de estas fuentes, listadas en orden cronológico.

1. Menger, K. (1927). "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10, 96 a 115.
2. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 a 168.
3. Harris, T. E. y Ross, F. S. (1955). Fundamentals of a Method for Evaluating Rail Net Capacities. Memorando de investigación RM-1573. Santa Monica: RAND Corporation.
4. Elias, P., Feinstein, A. y Shannon, C. E. (1956). "A Note on the Maximum Flow Through a Network." IRE Transactions on Information Theory 2(4), 117 a 119.
5. Ford, L. R. y Fulkerson, D. R. (1956). "Maximal Flow Through a Network." Canadian Journal of Mathematics 8, 399 a 404.
6. Gomory, R. E. y Hu, T. C. (1961). "Multi-Terminal Network Flows." Journal of the Society for Industrial and Applied Mathematics 9(4), 551 a 570.
7. Schwartz, B. L. (1966). "Possible Winners in Partially Completed Tournaments." SIAM Review 8(3), 302 a 308.
8. Edmonds, J. y Karp, R. M. (1972). "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." Journal of the ACM 19(2), 248 a 264.
9. Greig, D. M., Porteous, B. T. y Seheult, A. H. (1989). "Exact Maximum A Posteriori Estimation for Binary Images." Journal of the Royal Statistical Society, Series B 51(2), 271 a 279.
10. Nagamochi, H. y Ibaraki, T. (1992). "Computing Edge-Connectivity in Multigraphs and Capacitated Graphs." SIAM Journal on Discrete Mathematics 5(1), 54 a 66.
11. Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." En Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, 21 a 30.
12. Wu, Z. y Leahy, R. (1993). "An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation." IEEE Transactions on Pattern Analysis and Machine Intelligence 15(11), 1101 a 1113.
13. Hao, J. y Orlin, J. B. (1994). "A Faster Algorithm for Finding the Minimum Cut in a Directed Graph." Journal of Algorithms 17(3), 424 a 446.
14. Karger, D. R. y Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4), 601 a 640.
15. Stoer, M. y Wagner, F. (1997). "A Simple Min-Cut Algorithm." Journal of the ACM 44(4), 585 a 591.
16. Karger, D. R. (2000). "Minimum Cuts in Near-Linear Time." Journal of the ACM 47(1), 46 a 76.
17. Shi, J. y Malik, J. (2000). "Normalized Cuts and Image Segmentation." IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888 a 905.
18. Boykov, Y. y Jolly, M.-P. (2001). "Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images." En Proceedings of the 8th IEEE International Conference on Computer Vision, 105 a 112.
19. Schrijver, A. (2002). "On the History of the Transportation and Maximum Flow Problems." Mathematical Programming 91(3), 437 a 445.
20. Kawarabayashi, K. y Thorup, M. (2015). "Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time." En Proceedings of the 47th ACM Symposium on Theory of Computing, 665 a 674.
21. Li, J. (2021). "Deterministic Mincut in Almost-Linear Time." En Proceedings of the 53rd ACM Symposium on Theory of Computing, 384 a 395.
22. Chen, L., Kyng, R., Liu, Y. P., Peng, R., Probst Gutenberg, M. y Sachdeva, S. (2022). "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time." En Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science, 612 a 623.