메티스
METISMETIS는 다양한 멀티레벨 [1][2]알고리즘을 구현하는 그래프 분할용 소프트웨어 패키지입니다.METIS의 다단계 접근법에는 세 가지 단계가 있으며 각 단계에 대한 여러 알고리즘이 포함되어 있다.
- 그래프0 G, G1, ..., G의N 시퀀스를 생성하여 그래프를 조밀하게 만듭니다.여기서0 G는 원본 그래프이며 각 0 i i j j n N에 대해 G의i 정점 수가 G의j 정점 수보다 큽니다.
- GN 파티션 계산
- 파티션을 G, ..., G의0 순서로 순서대로N 투영하여 각 그래프에 대해 미세화합니다.
세 번째 단계(G에 투영된 세분화된 분할0) 동안 계산된 최종 분할은 원래 그래프의 분할이다.
레퍼런스
- ^ George Karypis & Vipin Kumar (1995). METIS - Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0 (Technical report).[영구 데드링크]
- ^ Karypis, G. & Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997.
외부 링크
