Coupe minimale

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ce qu'est une coupe

Une coupe partage les sommets d'un graphe en deux groupes non vides, S et le reste, V \ S. Les arêtes qui ont une extrémité dans chaque groupe traversent la coupe, et les supprimer déconnecte les deux groupes l'un de l'autre. Dans un graphe pondéré, le poids d'une coupe, aussi appelé sa capacité, est le poids total des arêtes qui la traversent ; dans un graphe non pondéré, c'est simplement leur nombre. Une coupe minimale est une coupe de poids minimal : la façon la moins coûteuse de casser le graphe en deux morceaux.

L'exemple suivi est un petit réseau informatique de 8 routeurs reliés par 15 liaisons. Chaque poids est la capacité d'une liaison en gigabits par seconde. Les routeurs A à D se trouvent dans un bâtiment et E à H dans un autre :

bâtiment 1 :  A-B 4   A-C 3   A-D 2   B-C 2   B-D 3   C-D 3
bâtiment 2 :  E-F 3   E-G 2   E-H 3   F-G 4   F-H 2   G-H 3
entre eux :   C-E 2   D-F 1   B-G 1

8 routeurs, 15 liaisons, capacité totale 38

Couper les trois liaisons entre les bâtiments, C-E, D-F et B-G, coûte 2 + 1 + 1 = 4 et coupe le réseau en deux. C'est la coupe minimale, et c'est la seule coupe de poids 4. C'est aussi le point faible du réseau : les deux bâtiments peuvent échanger au plus 4 gigabits par seconde, quelle que soit la configuration du reste du réseau. La coupe suivante la moins coûteuse isole le routeur H, pour un coût de 8, la somme de ses propres liaisons.

2. Deux problèmes sous le même nom

« Coupe minimale » désigne deux problèmes apparentés, et la plupart des confusions sur le sujet viennent de ce qu'on les mélange :

• Coupe s-t minimale. Deux sommets sont donnés, une source s et un puits t, et la coupe doit les séparer : s dans S, t à l'extérieur. C'est la coupe du théorème flot maximal / coupe minimale de la section 4. Dans l'exemple, la coupe minimale qui sépare A de H est la coupe des bâtiments, de poids 4, mais la coupe minimale qui sépare A de B a un poids de 9 : comme les deux sont dans le même bâtiment, l'option la moins coûteuse est d'isoler A seul.
• Coupe minimale globale. Aucun sommet n'est donné ; la coupe peut séparer deux groupes quelconques. Son poids est le plus petit de toutes les coupes s-t minimales, et dans un graphe non pondéré il est égal à l'arête-connexité λ(G), le plus petit nombre d'arêtes dont la suppression déconnecte le graphe. Les sections 5 à 7 la calculent.

Une borne simple relie les deux idées. Isoler un seul sommet coûte la somme des poids de ses liaisons, son degré pondéré, donc la coupe minimale globale ne peut jamais dépasser le plus petit degré. Hassler Whitney a prouvé la version non pondérée en 1932 : sommet-connexité ≤ arête-connexité ≤ degré minimum. Dans l'exemple, le plus petit degré pondéré est 8, en H, et la coupe minimale de 4 est bien en dessous : le point faible est un faisceau de liaisons entre deux groupes, pas un routeur isolé mal connecté. Sans les poids, la borne est atteinte ici : chaque routeur a au moins 3 liaisons, et 3 liaisons sont le plus petit nombre qui déconnecte le réseau.

3. Pourquoi essayer toutes les coupes ne passe pas à l'échelle

Un graphe à n sommets possède 2n-1 - 1 coupes : chaque sommet autre qu'un premier sommet fixé va d'un côté ou de l'autre, et la répartition qui met tout du même côté n'est pas une coupe. L'exemple en a 27 - 1 = 127, assez peu pour toutes les énumérer.

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):
    """Poids total des liaisons qui ont exactement une extrémité dans side."""
    return sum(w for u, v, w in links if (u in side) != (v in side))

def all_cuts(links):
    """Toutes les partitions des sommets en deux côtés non vides, chacune comptée une fois."""
    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 contient toujours le premier sommet
        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

Le nombre double à chaque sommet : 50 sommets donnent déjà plus de 560 000 milliards de coupes. Le reste de ce guide porte sur des algorithmes qui trouvent le minimum sans examiner la plupart d'entre elles. Le guide sur la complexité des algorithmes de graphes explique pourquoi une croissance exponentielle de ce type exclut la force brute.

4. Coupes s-t minimales par flot maximal

Le théorème flot maximal / coupe minimale, énoncé par Lester Ford et Delbert Fulkerson dans un rapport de la RAND de 1954 et publié en 1956, l'année même où Peter Elias, Amiel Feinstein et Claude Shannon en ont donné une preuve différente, affirme que le plus grand flot que l'on peut envoyer de s à t est égal au poids de la plus petite coupe qui les sépare. Un sens est facile : chaque unité de flot doit traverser chaque coupe s-t, donc aucun flot ne peut dépasser aucune coupe. Tout le contenu du théorème est que les deux se rejoignent toujours. Le guide sur les flots dans les réseaux et le théorème flot maximal / coupe minimale le démontre avec des chemins augmentants.

La question avait une origine militaire. En 1955, T. E. Harris et F. S. Ross, de la RAND Corporation, ont modélisé les chemins de fer de l'ouest de l'Union soviétique et de l'Europe de l'Est sous la forme d'un réseau de 44 sommets et 105 arêtes, pour trouver l'ensemble de lignes le moins coûteux à perturber. Ils s'intéressaient davantage à la coupe qu'au flot : leur rapport désigne une coupe minimale de 163 000 tonnes comme « le goulot d'étranglement ». Il n'a été déclassifié qu'en 1999.

Pour calculer des coupes, l'important est la manière dont la coupe découle d'un flot maximal. Lorsqu'il ne reste plus aucun chemin augmentant de s à t, rassemblez tous les sommets que s peut encore atteindre par les arêtes ayant de la capacité disponible, qui forment le graphe résiduel. Cet ensemble est le côté S d'une coupe minimale, et les arêtes saturées qui en sortent forment la coupe. Le programme ci-dessous exécute l'algorithme d'Edmonds-Karp, qui augmente toujours le long d'un plus court chemin, puis lit la coupe. Chaque liaison non orientée peut porter du flot dans les deux sens.

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):
    """Flot maximal d'Edmonds-Karp, puis la coupe s-t minimale lue sur le graphe résiduel."""
    cap = {}
    for u, v, w in links:                      # une liaison non orientée porte du flot dans les deux sens
        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:       # plus court chemin augmentant par 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:                      # consomme la capacité, ouvre le sens inverse
            cap[u][v] -= push
            cap[v][u] += push
        flow += push
    side = set(parent)                         # encore accessible depuis s dans le graphe résiduel
    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 à H, le flot maximal vaut 4, et il peut se décomposer en trois chemins portant 2, 1 et 1 unités. Ensuite, les trois liaisons entre les bâtiments sont saturées, A peut encore atteindre B, C et D mais rien au-delà, et la coupe est exactement la coupe des bâtiments. De A à B, le flot vaut 9 et la coupe isole A. Edmonds-Karp s'exécute en temps O(V E2) ; il existe des algorithmes de flot plus rapides, mais tout algorithme correct donne de cette façon une coupe s-t minimale.

Pour les graphes non pondérés, le théorème a une forme combinatoire célèbre, qui porte généralement le nom de Karl Menger, dont le théorème de 1927 est la version pour les sommets : le plus grand nombre de chemins de u à v qui ne partagent aucune arête est égal au plus petit nombre d'arêtes dont la suppression sépare u de v. Cette forme pour les arêtes du théorème de Menger découle du théorème flot maximal / coupe minimale. Dans l'exemple, sans tenir compte des poids, il y a trois chemins arêtes-disjoints de A à H, et trois liaisons entre les bâtiments.

5. Coupes minimales globales par flots maximaux

Une coupe minimale globale sépare une certaine paire de sommets ; c'est donc la plus petite coupe s-t sur l'ensemble des paires. Moins de paires suffisent. Fixez un sommet quelconque s : quelle que soit la coupe minimale, un sommet t se trouve de l'autre côté, donc le minimum sur les n - 1 choix de t la trouve. Dans l'exemple, en fixant s = A, les quatre exécutions avec t dans l'autre bâtiment renvoient toutes 4.

Ralph Gomory et T. C. Hu ont montré en 1961 que n - 1 flots maximaux révèlent bien davantage : ils construisent un arbre sur les mêmes sommets, appelé aujourd'hui arbre de Gomory-Hu, dans lequel la coupe minimale entre deux sommets quelconques est égale au plus petit poids d'arête sur le chemin de l'arbre qui les relie. Pour l'exemple, les sept arêtes de l'arbre portent les valeurs 4, 8, 9, 9, 10, 10 et 10, si bien que la valeur de chacune des 28 coupes minimales entre paires peut s'y lire, et la plus petite arête, 4, est la coupe minimale globale.

Les méthodes fondées sur les flots fonctionnent aussi pour les graphes orientés, et ce sont les bons outils lorsque la coupe minimale entre des sommets précis importe. Pour la coupe minimale globale d'un graphe non orienté, les deux algorithmes suivants sont plus simples et plus rapides.

6. L'algorithme de Stoer-Wagner

En 1997, Mechthild Stoer et Frank Wagner ont publié un algorithme qui trouve la coupe minimale globale d'un graphe non orienté à poids positifs ou nuls sans utiliser le moindre flot, en s'appuyant sur des travaux antérieurs de Hiroshi Nagamochi et Toshihide Ibaraki. Il se déroule en n - 1 phases. Chaque phase fait trois choses :

1. En partant d'un sommet quelconque, ajoutez les sommets un par un, en choisissant toujours celui qui est le plus fortement relié à ceux déjà ajoutés : le plus grand poids total de liaisons vers l'ensemble en croissance. Cet ordre est appelé recherche par adjacence maximale.
2. Lorsque le dernier sommet t est ajouté, le poids de ses liaisons vers tout le reste est la coupe de la phase. Un court argument montre que c'est une coupe minimale qui sépare t de s, le sommet ajouté juste avant lui.
3. Fusionnez s et t en un seul sommet, en additionnant les poids des liaisons parallèles, et commencez la phase suivante sur le graphe réduit.

Soit la coupe minimale globale sépare s de t, auquel cas cette phase l'a trouvée, soit elle les garde du même côté, auquel cas les fusionner ne fait rien perdre. Après n - 1 phases, la plus petite des coupes de la phase est la réponse.

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):
    """Coupe minimale globale : n - 1 phases, chacune se terminant par une coupe de la phase et une fusion."""
    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}                 # les sommets fusionnés retiennent ce qu'ils contiennent
    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:                        # ajoute ensuite le sommet le plus fortement relié
            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():          # fusionne t dans 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')

Sur l'exemple, la première phase se termine en H avec une coupe de 8, le coût de son isolement. À mesure que les phases fusionnent des sommets, les groupes grossissent : à la phase 4, le dernier sommet ajouté est le groupe fusionné E, F, G, H, et sa coupe de la phase est la coupe des bâtiments, 4. Les phases restantes ne trouvent que des coupes plus grandes. Avec un tas de Fibonacci pour le choix « le plus fortement relié », chaque phase prend O(E + V log V) et l'algorithme complet O(V E + V2 log V); la version simple ci-dessus, qui cherche le maximum par un balayage, prend O(V3).

7. La contraction aléatoire de Karger

L'algorithme de David Karger, de 1993, est l'un des algorithmes randomisés les plus célèbres. Il est presque trop simple pour fonctionner :

1. Choisissez une liaison au hasard, avec une probabilité proportionnelle à son poids, et contractez-la : fusionnez ses deux extrémités en un seul sommet, en supprimant les liaisons qui les relient.
2. Répétez jusqu'à ce qu'il ne reste que deux sommets fusionnés.
3. Les liaisons entre ces deux sommets forment une coupe. Renvoyez-la.

Une exécution peut facilement échouer : si elle contracte à un moment une liaison de la coupe minimale, cette coupe est perdue. La surprise, c'est qu'elle échoue assez rarement. Une coupe minimale est légère, donc les choix aléatoires tendent à éviter ses liaisons, et Karger a prouvé qu'une seule exécution renvoie une coupe minimale donnée avec une probabilité d'au moins 2 / (n (n - 1)). Répéter l'exécution et garder la coupe la plus légère fait baisser la probabilité d'échec aussi vite que vous le souhaitez.

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):
    """Une exécution de l'algorithme de Karger : fusionne les extrémités de liaisons aléatoires jusqu'à ce qu'il reste deux groupes."""
    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]   # les liaisons plus lourdes fusionnent plus souvent
        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

Sur 10 000 exécutions sur l'exemple, la coupe minimale est sortie 3 228 fois, soit environ 32 %, neuf fois les 3,6 % garantis. Garder la meilleure de 10 exécutions l'a trouvée dans 978 essais sur 1 000. La garantie est un pire cas : en ne comptant que sur elle, il faudrait 127 exécutions pour une confiance de 99 % sur 8 sommets. La borne de Karger a aussi une conséquence frappante. Chaque coupe minimale est trouvée avec une probabilité d'au moins 2 / (n (n - 1)), et ces événements ne peuvent pas se produire en même temps, donc un graphe peut avoir au plus n (n - 1) / 2 coupes minimales. Un cycle à n sommets en a exactement autant : supprimer deux quelconques de ses arêtes donne une coupe minimale.

David Karger et Clifford Stein ont amélioré la méthode en 1996 en ne contractant qu'une partie du chemin, puis en poursuivant récursivement sur deux copies, ce qui donne un algorithme en O(n2 log3 n) qui trouve une coupe minimale avec forte probabilité. Karger a ensuite donné un algorithme qui s'exécute en temps quasi linéaire en le nombre d'arêtes.

8. Quel algorithme utiliser

En pratique : pour la coupe entre deux sommets donnés, exécutez un flot maximal. Pour la coupe minimale globale d'un graphe non orienté, Stoer-Wagner est le choix déterministe standard, et c'est ce qu'implémentent des bibliothèques comme NetworkX. L'algorithme de Karger est celui vers lequel se tourner lorsque le graphe est grand, lorsque le calcul peut être réparti sur de nombreuses machines, ou lorsqu'il vous faut toutes les coupes minimales plutôt qu'une seule.

9. Graphes orientés et coupes de sommets

Dans un graphe orienté, une coupe (S, V \ S) ne compte que les arcs qui vont de S vers l'autre côté ; les arcs qui reviennent n'aident en rien à la déconnexion. Stoer-Wagner et l'algorithme de Karger reposent sur la symétrie et ne s'appliquent pas. La coupe minimale globale peut tout de même être trouvée avec des flots maximaux, d'un sommet fixé vers chacun des autres et en retour, et Jianxiu Hao et James Orlin ont montré en 1994 comment le faire en à peu près le temps d'un seul calcul de flot.

Parfois, la question est de savoir quels sommets supprimer plutôt que quelles arêtes : les routeurs dont la panne couperait le réseau en deux. Le plus petit ensemble de ce type donne la sommet-connexité, et une astuce classique la ramène aux coupes d'arêtes, en dédoublant chaque sommet en une copie « entrée » et une copie « sortie » reliées par une arête de capacité 1. Un sommet seul dont la suppression déconnecte le graphe est un point d'articulation, et une arête seule qui le fait est un pont. Les deux peuvent être trouvés en temps linéaire sans flots, comme le guide sur les composantes connexes, ponts et points d'articulation l'explique.

10. Où servent les coupes minimales

• Fiabilité des réseaux. La coupe minimale globale d'un réseau de communication ou d'électricité est son point le plus faible : le plus petit nombre de liaisons, ou la plus petite capacité, dont la panne le coupe en deux. La coupe s-t minimale est le goulot d'étranglement entre deux sites, comme dans l'exemple.
• Segmentation d'images. Faites de chaque pixel un sommet relié à ses voisins, avec des liaisons lourdes entre pixels semblables, et ajoutez une source pour « objet » et un puits pour « fond ». Une coupe s-t minimale sépare l'objet du fond le long de la frontière qui coupe les liaisons les plus faibles. D. M. Greig, B. T. Porteous et A. H. Seheult ont été les premiers à utiliser des coupes minimales en analyse d'images, en 1989, pour restaurer des images binaires bruitées, Zhenyu Wu et Richard Leahy les ont appliquées à la segmentation en 1993, et les coupes de graphes interactives de Yuri Boykov ont fait de la méthode un outil standard de la vision par ordinateur.
• Partitionnement (clustering). Une coupe minimale divise un graphe de similarité là où il est le plus faible. Employée seule, elle tend à isoler quelques points faiblement rattachés, c'est pourquoi Jianbo Shi et Jitendra Malik ont introduit la coupe normalisée, qui divise le poids de la coupe par la taille de chaque côté.
• Sélection de projets. Choisir des projets qui rapportent de l'argent mais exigent des prérequis coûteux est un problème de coupe minimale déguisé : les projets rentables sont rattachés à la source, les coûts au puits, et les prérequis deviennent des arcs de capacité infinie. Le guide sur le choix des investissements résout un tel portefeuille de cette manière.
• Élimination sportive. Savoir si une équipe peut encore finir première, compte tenu des matchs restants, est une question de flot maximal, et la coupe minimale certifie un « non », comme Benjamin Schwartz l'a montré pour le baseball en 1966.

Le problème opposé, la coupe maximale, qui demande la partition avec le plus possible d'arêtes traversantes, semble similaire mais est NP-difficile. Minimiser une coupe est facile parce que c'est le dual d'un flot ; la maximiser n'offre aucune structure de ce genre.

11. Progrès récents

Les coupes minimales ont connu certaines des avancées récentes les plus frappantes de l'algorithmique. En 2015, Ken-ichi Kawarabayashi et Mikkel Thorup ont trouvé un algorithme déterministe pour la coupe minimale globale d'un graphe simple non pondéré qui s'exécute en temps quasi linéaire. En 2021, Jason Li a étendu le temps presque linéaire déterministe aux graphes pondérés. Et en 2022, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg et Sushant Sachdeva ont montré que le flot maximal avec des capacités entières, et avec lui la coupe s-t minimale, peut être calculé en temps presque linéaire m1 + o(1), un résultat qui a reçu le prix du meilleur article à FOCS 2022. Ces algorithmes ne sont pas encore ceux qu'utilisent les logiciels pratiques, mais ils établissent à quelle vitesse ces problèmes peuvent être résolus en principe.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les théorèmes, algorithmes et attributions ci-dessus proviennent des sources suivantes, classées par ordre chronologique.

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