Algorithme de Kernighan-Lin

L'algorithme de Kernighan–Lin est une heuristique pour réaliser un partitionnement de graphe. L'algorithme est notamment utilisé pour l'agencement des circuits intégrés et des composants pour l'intégration à très grande échelle (VLSI)^[1]^,^[2].

Description modifier

L'algorithme prend en entrée un graphe non-orienté $G = (V, E)$ , défini par l'ensemble de nœuds $V$ , l'ensemble de liens $E$ et potentiellement les coûts des liens de $E$ . L'objectif est de réaliser une partition de l'ensemble $V$ en deux ensembles disjoints $A$ et $B$ de tailles proches ou égales, de manière à minimiser la somme $T$ des poids du sous-ensemble de liens allant de $A$ à $B$ . Si le graphe est non-pondéré, l'algorithme cherche à minimiser le nombre de liens allant de $A$ à $B$ , ce qui est équivalent à assigner un poids unitaire à tous les liens.

L'algorithme tient à jour une partition et l'améliore à chaque itération en utilisant une méthode gloutonne. Le principe est d'apparier des nœuds de $A$ à des nœuds de $B$ , de manière qu'intervertir les ensembles auxquels appartiennent les nœuds appariés améliore la qualité du partitionnement. Après association des nœuds, l'algorithme réalise un sous-ensemble des paires choisies pour obtenir la valeur minimum de $T$ . Pour un graphe à $n$ nœuds, chaque itération de l'algorithme est réalisée en $O (n 2 log n)$ .

Plus précisément, pour tout $a\in A$ , on appelle $I_{a}$ le coût interne de $a$ , c'est-à-dire la somme des coûts des liens entre $a$ et les autres nœuds de $A$ et $E_{a}$ le coût externe de $a$ , c'est-à-dire la somme des coûts des liens entre $a$ et les nœuds de $B$ . On définit de manière analogue $I_{b}$ et $E_{b}$ pour tout $b\in B$ . On pose

D_{x}=E_{x}-I_{x}

la différence entre les coûts externes et internes de $x$ . Si $a$ et $b$ sont intervertis, alors la réduction de coût est:

T_{old}-T_{new}=D_{a}+D_{b}-2c_{a,b}

où $c_{a,b}$ est le coût d'un potentiel lien entre $a$ et $b$ .

L'algorithme cherche à trouver une suite optimale d'interversions entre éléments de $A$ et de $B$ qui maximise $T_{old}-T_{new}$ puis met à jour le partitionnement du graphe en $A$ et $B$ en réalisant effectivement ces opérations^[1].

Pseudocode modifier

Source^[1]

fonction Kernighan-Lin(G(V, E))
    déterminer une partition initiale des nœuds équilibrée entre les ensembles A et B
    
    faire
        calculer les valeurs D pour tout a dans A et tout b dans B
        soient L_g, L_a, et L_b des listes vides 
        pour n := 1 à |V| faire
            trouver a dans A et b dans B tels que g = D[a] + D[b] − 2×c(a, b) est maximum
            on ne considère plus a et b dans la suite de cette itération
            ajouter g à L_g, a à L_a et b à L_b
            mettre à jour les valeurs D pour les éléments de A = A \ a et B = B \ b
        fin pour
        trouver k qui maximise g_max, la somme des L_g[1], ..., L_g[k]
        si g_max > 0 alors
            Mettre L_a[1], L_a[2], ..., L_a[k] dans B et L_b[1], L_b[2], ..., L_b[k] dans A
    jusqu'à (g_max ≤ 0)

    renvoyer A,B

Références modifier

↑ ^{a b et c} B. W. Kernighan et Shen Lin, « An efficient heuristic procedure for partitioning graphs », Bell System Technical Journal, vol. 49,‎ 1970, p. 291–307 (DOI 10.1002/j.1538-7305.1970.tb01770.x)
↑ C. P Ravikumar, Parallel methods for VLSI layout design, Greenwood Publishing Group, 1995, 73 p. (ISBN 978-0-89391-828-6, lire en ligne)

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kernighan–Lin algorithm » (voir la liste des auteurs).

Portail des mathématiques

[kl-1] {a b et c} B. W. Kernighan et Shen Lin, « An efficient heuristic procedure for partitioning graphs », Bell System Technical Journal, vol. 49,‎ 1970, p. 291–307 (DOI 10.1002/j.1538-7305.1970.tb01770.x)

[ravikumar-2] C. P Ravikumar, Parallel methods for VLSI layout design, Greenwood Publishing Group, 1995, 73 p. (ISBN 978-0-89391-828-6, lire en ligne)

[1]

[2]