Kernighan-Lin-Algorithmus

Der Kernighan-Lin-Algorithmus ist ein 1969 formulierter heuristischer Algorithmus von Brian W. Kernighan und Shen Lin, um das Graphpartitionierungsproblem zu lösen. In der Praxis wird er eingesetzt, um die Komponentenplatzierung auf einem Chip zu optimieren. Dabei soll die Länge der Leitungen zwischen den Komponenten minimal gehalten werden.

Sei ${\displaystyle G}$ ein kantengewichteter Graph mit Knotenmenge ${\displaystyle V}$ und Kantenmenge ${\displaystyle E}$. Der Algorithmus soll ${\displaystyle V}$ in zwei disjunkte Untermengen A und B gleicher Größe aufteilen, sodass die Summe ${\displaystyle T}$ der Kantengewichte zwischen A und B minimal wird. Die internen Kosten von A, also die Summe aller Kantengewichte abgehend vom Knoten a in A, wird als ${\displaystyle I_{a}}$ bezeichnet. ${\displaystyle E_{a}}$ seien die externen Kosten vom Knoten a, also die Summe aller Kosten der Kanten zwischen a und den Knoten in B.

${\displaystyle D_{a}=E_{a}-I_{a}}$

ist die Differenz der externen und internen Kantengewichte. Werden Knoten a und b getauscht, so ist

${\displaystyle T_{\text{alt}}-T_{\text{neu}}=D_{a}+D_{b}-2c_{a,b}}$,

hierbei sind ${\displaystyle c_{a,b}}$ die Kosten der Kante zwischen a und b.

Der Algorithmus versucht nun, die Elemente der Mengen A und B optimal zu tauschen, sodass ${\displaystyle T_{\text{alt}}-T_{\text{neu}}}$ maximal wird.^[1]

1. ↑ B. W. Kernighan, Shen Lin: An efficient heuristic procedure for partitioning graphs. In: Bell Systems Technical Journal. 49. Jahrgang, 1970, S. 291–307 (uwindsor.ca [PDF]).