Un algoritmo multilevel para la partición de grafos

El problema de partición de grafos consiste en dividir los vértices de un grafo en conjuntos de tamaños específicos de modo que pocos bordes crucen entre conjuntos. Este problema NP-completo surge en muchos problemas científicos y de ingeniería importantes. Ejemplos prominentes incluyen la descomposición de estructuras de datos para cómputo paralelo, la colocación de elementos de circuitos y el ordenamiento de cálculos de matrices dispersas. Presentamos un algoritmo multilevel para la partición de grafos en el cual el grafo es aproximado por una secuencia de grafos cada vez más pequeños. El grafo más pequeño se particiona utilizando un método espectral, y esta partición se propaga de regreso a través de la jerarquía de grafos. Se aplica periódicamente una variante del algoritmo de Kernighan-Lin para refinar la partición. Todo el algoritmo puede implementarse para ejecutarse en un tiempo proporcional al tamaño del grafo original. Los experimentos indican que, en comparación con otros métodos avanzados, el algoritmo multilevel produce particiones de alta calidad a bajo costo.