METIS es un paquete de software para la partición de gráficos que implementa varios algoritmos multinivel . [1] [2] El enfoque multinivel de METIS tiene tres fases y viene con varios algoritmos para cada fase:
- Coarsen el gráfico generando una secuencia de gráficos G 0 , G 1 , ..., G N , donde G 0 es el gráfico original y para cada 0 ≤ i ≤ j ≤ N, el número de vértices en G i es mayor que el número de vértices en G j .
- Calcule una partición de G N
- Proyecte la partición hacia atrás a través de la secuencia en el orden de G N , ..., G 0 , refinándola con respecto a cada gráfico.
La partición final calculada durante la tercera fase (la partición refinada proyectada sobre G 0 ) es una partición del gráfico original.
Referencias
- ^ George Karypis y Vipin Kumar (1995). METIS - Sistema de ordenación de matrices dispersas y particiones de gráficos no estructurados, versión 2.0 (informe técnico).[ enlace muerto permanente ]
- ^ Karypis, G. y Kumar, V. (1999). "Un esquema multinivel rápido y de alta calidad para particionar gráficos irregulares". Revista SIAM de Computación Científica . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi : 10.1137 / S1064827595287997 .