Algorithme de Kernighan-Lin
# 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)^,.$

## Description

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.

## Pseudocode

Source

