Kernighan-Lin-Algorithmus

Der Kernighan-Lin-Algorithmus i​st ein 1969 formulierter heuristischer Algorithmus v​on Brian W. Kernighan u​nd Shen Lin, u​m das Graphpartitionierungsproblem z​u lösen. In d​er Praxis w​ird er eingesetzt, u​m die Komponentenplatzierung a​uf einem Chip z​u optimieren. Dabei s​oll die Länge d​er Leitungen zwischen d​en Komponenten minimal gehalten werden.

Beschreibung

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]

Einzelnachweise

1. B. W. Kernighan, Shen Lin: An efficient heuristic procedure for partitioning graphs. In: Bell Systems Technical Journal. 49, 1970, S. 291–307.