METIS

METIS es un paquete de software para la partición de grafos que implementa varios algoritmos multinivel. El enfoque multinivel de METIS tiene tres fases y viene con varios algoritmos para cada fase: Reducir el grafo generando una secuencia de grafos G0, G1, ..., GN, donde G0 es el grafo original y para cada 0 ≤ i ≤ j ≤ N, el número de vértices en Gi es mayor que el número de vértices en Gj. Calcular una partición de GN Proyectar la partición de vuelta a través de la secuencia en el orden de GN, ..., G0, refinándola con respecto a cada grafo. La partición final calculada durante la tercera fase (la partición refinada proyectada sobre G0) es una partición del grafo original. Referencias Enlaces externos Sitio web de METIS Algoritmos de grafos Software matemático