Algoritmos Multinivel para la Partición de Grafos con Múltiples Restricciones

Los algoritmos tradicionales de partición de grafos calculan una partición k-vía de un grafo de manera que se minimiza el número de aristas que son cortadas por la partición y cada partición tiene un número igual de vértices. La tarea de minimizar el corte de aristas puede considerarse como el objetivo y el requisito de que las particiones sean del mismo tamaño puede considerarse como la restricción. En este artículo, ampliamos el problema de partición incorporando un número arbitrario de restricciones de equilibrio. En nuestra formulación, se asigna un vector de pesos a cada vértice, y el objetivo es producir una partición k-vía de modo que la partición satisfaga una restricción de equilibrio asociada a cada peso, mientras se intenta minimizar el corte de aristas. Las aplicaciones de este problema de partición de grafos con múltiples restricciones incluyen la solución paralela de cálculos multiphysicos y multifásicos, que subyacen a muchas simulaciones científicas a gran escala existentes y emergentes. Presentamos nuevas partes de grafos con múltiples restricciones...