Algoritmo de Kernighan-Lin

El algoritmo de Kernighan-Lin es un algoritmo heurístico para encontrar particiones de grafos . El algoritmo tiene una importante aplicación práctica en el diseño de circuitos y componentes digitales en la automatización del diseño electrónico de VLSI . ^{[ 1 ] [ 2 ]}

La entrada del algoritmo es un grafo no dirigido G = ( V , E ) con conjunto de vértices V , conjunto de aristas E , y (opcionalmente) pesos numéricos en las aristas de E . El objetivo del algoritmo es particionar V en dos subconjuntos disjuntos A y B de igual (o casi igual) tamaño, de manera que se minimice la suma T de los pesos del subconjunto de aristas que cruzan de A a B . Si el grafo no tiene pesos, entonces el objetivo es minimizar el número de aristas que se cruzan; esto es equivalente a asignar un peso de uno a cada arista. El algoritmo mantiene y mejora una partición, en cada pasada utilizando un algoritmo voraz para emparejar vértices de A con vértices de B , de modo que mover los vértices emparejados de un lado de la partición al otro mejorará la partición. Después de emparejar los vértices, realiza un subconjunto de los pares elegidos para tener el mejor efecto general en la calidad de la solución T . Dado un grafo con n vértices, cada pasada del algoritmo se ejecuta en un tiempo O ( n ² log n ) .

En más detalle, para cada${\displaystyle a\in A}$, dejar${\displaystyle I_{a}}$Sea el costo interno de un , es decir, la suma de los costos de las aristas entre un y otros nodos en A , y sea${\displaystyle E_{a}}$sea ​​el costo externo de a , es decir, la suma de los costos de las aristas entre a y los nodos en B. De manera similar, defina${\displaystyle I_{b}}$,${\displaystyle E_{b}}$para cada${\displaystyle b\in B}$Además, dejemos

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

Sea la diferencia entre los costos externos e internos de s . Si a y b se intercambian, entonces la reducción en el costo es

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

dónde${\displaystyle c_{a,b}}$es el costo de la posible arista entre a y b .

El algoritmo intenta encontrar una serie óptima de operaciones de intercambio entre elementos de${\displaystyle A}$y${\displaystyle B}$que maximiza${\displaystyle T_{antiguo}-T_{nuevo}}$^{y luego ejecuta las operaciones, produciendo} una partición del grafo en A y B. ^{[ 1} ]

Fuente: ^{[ 2 ]}

la función Kernighan-Lin ( G(V, E) ) es determinar una partición inicial equilibrada de los nodos en los conjuntos A y B hacer Calcular los valores de D para todos los valores de a en A y b en B. Sean gv, av y bv listas vacías. para n := 1 hasta |V| / 2 hacer Encuentra a de A y b de B, de tal manera que g = D[a] + D[b] − 2×c(a, b) sea máximo. Eliminar a y b de la consideración posterior en esta pasada suma g a gv, a a av y b a bv. Actualizar los valores D para los elementos de A = A \ a y B = B \ b fin para encontrar k que maximice g_max, la suma de gv[1], ..., gv[k] si g_max > 0 entonces Intercambie av[1], av[2], ..., av[k] por bv[1], bv[2], ..., bv[k] hasta que (g_max ≤ 0)devolver G(V, E)

• Algoritmo de Fiduccia-Mattheyses