Un enfoque clásico para resolver el problema de bipartición de Hypergraph es una heurística iterativa de Charles Fiduccia y Robert Mattheyses. [1] Esta heurística se denomina comúnmente algoritmo FM.
Introducción
El algoritmo FM es una heurística de tiempo lineal para mejorar las particiones de red. Nuevas características de la heurística KL :
Tiene como objetivo reducir los costos de corte neto; el concepto de tamaño de corte se extiende a los hipergrafos.
Sólo se mueve un único vértice a través del corte en un solo movimiento.
Los vértices están ponderados.
Puede manejar particiones "no balanceadas"; se introduce un factor de equilibrio.
Se utiliza una estructura de datos especial para seleccionar los vértices que se moverán a través del corte para mejorar el tiempo de ejecución.
Complejidad temporal O ( P ), donde P es el número total de terminales.
Ejemplo de FM
Heurística F–M: notación
Entrada: Un hipergrafo con un conjunto de vértices (celdas) y un conjunto de hiperaristas (redes)
n(i): número de celdas en la red i; p. ej., n(1) = 4
s(i): tamaño de la celda i
p(i): # de pines de la celda i; p. ej., p(1) = 4
C: número total de celdas; p. ej., C = 13
N: número total de redes; p. ej., N = 4
P: número total de pines; P = p(1) + … + p(C) = n(1) + … + n(N)
^ Fiduccia; Mattheyses (1982). "Una heurística de tiempo lineal para mejorar las particiones de red". XIX Conferencia de Automatización del Diseño . págs. 175–181. doi :10.1109/DAC.1982.1585498. ISBN .0-89791-020-6. Recuperado el 23 de octubre de 2013 .
