Un algoritmo de partición bidireccional de dos niveles

Se presenta un algoritmo de partición bidireccional que mejora significativamente los resultados altamente inestables de los algoritmos tradicionales basados en Kernighan-Lin. El algoritmo agrupa componentes fuertemente conectados en clústeres y reorganiza los clústeres en dos subconjuntos finales con tamaños especificados. Se sabe que las operaciones de agrupamiento reducen la complejidad y, por lo tanto, mejoran los resultados de particionamiento de circuitos muy grandes. Sin embargo, si el agrupamiento es inapropiado, los resultados de la partición pueden degenerar. Para prevenir la degeneración, los autores utilizan un enfoque de corte de razón para realizar el agrupamiento. A través de una serie de experimentos basados en la compensación entre la capacidad de corte y el tiempo de CPU, los autores determinan un valor óptimo para controlar el número resultante de grupos. Se han observado buenos resultados experimentales en términos de capacidad de corte y tiempo de CPU.