Paquete de software para la partición de gráficos
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:
- Haga más burdo 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 .
- Calcular 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.
Según los autores de Metis, Karypis y Kumar, "Metis es la palabra griega para sabiduría. Metis era una titánide en la mitología griega. Era la consorte de Zeus y la madre de Atenea. Presidía toda la sabiduría y el conocimiento". [3]
Referencias
- ^ George Karypis y Vipin Kumar (1995). METIS - Sistema de ordenamiento de matrices dispersas y particionamiento 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 grafos irregulares". Revista SIAM de Computación Científica . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi :10.1137/S1064827595287997. S2CID 3628209.
- ^ Karypis, George; Kumar, Vipin (1997). METIS: Un paquete de software para particionar gráficos no estructurados, particionar mallas y calcular ordenamientos de matrices dispersas que reducen el relleno (informe). hdl :11299/215346.
Enlaces externos
