불규칙 그래프 분할을 위한 빠르고 고품질의 다중 수준 스킴

최근 여러 연구자들이 정점과 간선을 병합하여 그래프 크기를 줄이고, 축소된 그래프를 분할한 뒤 다시 확장하여 원래 그래프의 분할을 구성하는 그래프 분할 알고리즘 계열을 연구하였다 4, 26. 초기 연구에서는 다중 수준 기법이 큰 잠재력을 가진다는 점이 명확했으나, 다양한 응용 분야에서 발생하는 그래프에 대해 일관되게 고품질 분할을 생성할 수 있는지는 알려지지 않았다. 우리는 세 단계를 모두 위한 다양한 선택지들의 효과를 조사했다: 축소, 가장 축소된 그래프의 분할, 그리고 세분화. 특히, 다중 수준 세분화 후 최종 분할 크기와 근접한 크기를 가지는 새로운 축소 휴리스틱(heavy-edge heuristic)을 제시한다. 또한, 확장 과정 중 세분화를 위한 훨씬 빠른 Kernighan-Lin 알고리즘 변형을 제시한다. 우리는 테스트...