Un algoritmo de bisección de redes rápido y robusto

La partición es un problema fundamental en diversos campos de estudio, como el reconocimiento de patrones, el procesamiento paralelo y el diseño de circuitos VLSI. Recientemente, varios autores han demostrado que el agrupamiento (clustering) o compactación de nodos mejora el rendimiento de los algoritmos de partición iterativos. Sin embargo, el clustering se ha utilizado principalmente como un paso de preprocesamiento antes de la partición en los métodos existentes. El artículo describe una técnica para extraer conglomerados utilizando información recopilada durante una pasada de un algoritmo de intercambio iterativo. Se analizan enfoques alternativos para la implementación de esta nueva técnica de clustering y se elige uno de ellos para incorporarlo en un algoritmo de Fiduccia-Mattheyses modificado (C.M. Fiduccia, R.M. Mattheyses, 1982) basado en un equilibrio entre el tiempo de ejecución y el rendimiento. El algoritmo resultante, BISECT, presenta un buen rendimiento en comparación con las variantes del algoritmo de Kernighan-Lin, incluidos el algoritmo de Fiduccia-Mattheyses, los enfoques locales y el simulated annealing en una amplia variedad de benchmarks reales y generados aleatoriamente. BISECT también se utiliza para encontrar separadores de vértices pequeños y sus resultados se comparan con métodos anteriores en varios benchmarks. Los resultados empíricos muestran que BISECT es estable y no es muy sensible a la partición inicial. Bajo supuestos adecuadamente moderados, se puede demostrar que BISECT se ejecuta en tiempo lineal. Los resultados empíricos confirman la velocidad de BISECT, que puede particionar grafos muy grandes (12,598 nodos y 91,961 aristas) en menos de seis minutos de tiempo de CPU en una estación de trabajo Sun Sparc 1+.>