Quelltext der Seite Kernighan-Lin-Algorithmus

Der '''Kernighan-Lin-Algorithmus''' ist ein 1969 formulierter [[Heuristik#Informatik|heuristischer Algorithmus]] von [[Brian W. Kernighan]] und [[Shen Lin]], um das [[Graphpartitionierung]]sproblem 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.

== Beschreibung ==
Sei <math>G</math> ein [[kantengewichteter Graph]] mit Knotenmenge <math>V</math> und Kantenmenge <math>E</math>. 
Der Algorithmus soll <math>V</math> in zwei disjunkte Untermengen A und B gleicher Größe aufteilen, sodass die Summe <math>T</math> 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 <math>I_a</math> bezeichnet. <math>E_a</math> seien die externen Kosten vom Knoten a, also die Summe aller Kosten der Kanten zwischen a und den Knoten in B.
:<math>D_{a} = E_{a} - I_{a}</math>
ist die Differenz der externen und internen Kantengewichte.
Werden Knoten a und b getauscht, so ist
:<math>T_\text{alt} - T_\text{neu} = D_a + D_b - 2c_{a,b}</math>,
hierbei sind
<math>c_{a,b}</math> die Kosten der Kante zwischen a und b.

Der Algorithmus versucht nun, die Elemente der Mengen A und B optimal zu tauschen, sodass <math>T_\text{alt} - T_\text{neu}</math> maximal wird.<ref name="kl">{{cite journal|first1=B. W.|last1=Kernighan|first2=Shen|last2=Lin| year = 1970 | title = An efficient heuristic procedure for partitioning graphs | journal = Bell Systems Technical Journal|volume=49|pages=291–307|url=http://files.vlsi.uwindsor.ca/88-559/page6/files/kl_paper.pdf}}</ref>

== Einzelnachweise == 
<references />

[[Kategorie:Algorithmus (Graphentheorie)]]