kahypar
v.1.3.5
하이퍼 그래프는 그래프의 일반화로, 각 (하이퍼) 가장자리 (순이라고도 함)는 두 개의 정점을 연결할 수 있습니다. K- 웨이 하이퍼 그래프 파티셔닝 문제는 잘 알려진 그래프 파티셔닝 문제의 일반화입니다. vertex를 vertex를 경계 크기의 K 분리 블록으로 설정하고 (평균 블록 크기의 최대 1 + ε), 그물에 정의 된 목적 함수를 최소화합니다.
가장 두드러진 두 가지 객관적인 기능은 컷 -Net과 연결성 (또는 λ-1) 메트릭입니다. Cut-Net은 그래프 파티셔닝에서 가장자리 컷 목표의 간단한 일반화입니다 (즉, 하나 이상의 블록을 연결하는 그물의 가중치의 합을 최소화 함). 연결 메트릭은 추가로 인터넷에 연결된 블록의 실제 숫자 λ를 고려합니다. 모든 네트의 (λ-1)-값을 합산함으로써, 하나는 평행 한 스파 스 매트릭스 벡터 곱셈의 총 통신 볼륨을 정확하게 모델링하고 한 번 더 일반 그래프의 에지 컷으로 되돌아가는 메트릭을 얻습니다.
Kahypar는 컷 및 (λ-1)- 메트릭을 최적화하기위한 다단계 하이퍼 그래프 파티셔닝 프레임 워크입니다. 재귀 이등분 과 직접 K- 웨이 파티셔닝을 모두 지원합니다. 다단계 알고리즘으로서, 3 단계로 구성됩니다. 조잡한 단계 에서, 초판은 더 작은 하이퍼 그래프의 계층 구조를 얻기 위해 조잡합니다. 두 번째 단계에서 초기 분할 알고리즘을 가장 작은 하이퍼 그래프에 적용한 후, 거친 것은 취소되며, 각 레벨에서, 로컬 검색 방법은 거친 레벨에 의해 유도 된 파티션을 개선하는 데 사용됩니다. Kahypar는 가장 극단적 인 버전으로 다단계 접근법을 인스턴스화하여 모든 수준의 계층 구조에서 단일 정점 만 제거합니다. 강력한 로컬 검색 휴리스틱과 결합 된이 매우 미세한 N- 레벨 접근법을 사용함으로써 매우 고품질의 솔루션을 계산합니다. 알고리즘과 자세한 실험 결과는 여러 연구 간행물에 제시됩니다.
가변적 인 블록 가중치를 가진 하이퍼 그래프 파티셔닝
Kahypar는 가변 블록 가중치를 지원합니다. 명령 줄 옵션 --use-individual-part-weights=true 사용되는 경우, 파티션은 각 블록 VX가 최대 BX의 가중치를 갖도록 하이퍼 그래프를 분할하려고 시도하며, 여기서 BX는 명령 줄 매개 변수를 사용하여 각 블록에 대해 --part-weights= B1 B2 B3 ... Bk-1 으로 지정할 수 있습니다. 프레임 워크는 아직 완벽하게 균형 잡힌 파티셔닝을 지원하지 않기 때문에 상한은 하이퍼 그래프의 모든 정점의 총 중량보다 약간 더 커야합니다. 이 기능은 여전히 실험적입니다.
고정 정점을 사용한 하이퍼 그래프 파티셔닝
고정 정점을 사용한 하이퍼 그래프 분할은 표준 하이퍼 그래프 파티셔닝의 변형입니다. 이 문제에서는 일부 정점의 블록 할당에 대한 추가 제약이 있습니다. 즉, 일부 정점은 나머지 "무료"정점을 분할 한 후에 고정 된 정점이 여전히 할당 된 블록에있는 조건으로 분할하기 전에 특정 블록에 사전 할 수 있습니다. 명령 줄 매개 변수 --fixed / -f hmetis 수정 파일 형식의 수정 파일을 지정하는 데 사용될 수 있습니다. V 정점이있는 하이퍼 그래프의 경우 수정 파일은 V 라인으로 구성됩니다. i th line은 vertex가 자유롭게 움직일 수 있음을 나타 내기 위해 -1 포함 하거나이 정점이 <part id> <part id> 차단하기 위해 사전 할 수 있어야 함을 나타냅니다. 부품 ID는 0부터 시작합니다.
Kahypar는 현재 고정 정점과의 분할을위한 세 가지 다른 수축 정책을 지원합니다.
free_vertex_only 수축 파트너가 자유 정점 인 모든 수축을 허용하고, 즉, 두 정점이 모두 자유롭거나 하나의 정점이 고정되어 있고 다른 정점은 자유로운 정점 쌍의 수축을 허용합니다.fixed_vertex_allowed 추가로 둘 다 동일한 블록에 사전 할 수있는 경우 두 개의 고정 정점의 수축이 가능합니다. 예비 실험을 기반으로, 이것은 현재 기본 정책입니다.equivalent_vertices 동일한 블록에 사전 할 수있는 두 개의 자유 정점 또는 2 개의 고정 된 정점으로 구성된 정점 쌍의 수축 만 허용합니다.진화 프레임 워크 (Kahypar-e)
Kahypar-e는 GECCO'18 간행물에 설명 된대로 진화론 적 틀로 Kahypar를 향상시킵니다. 상당히 많은 양의 실행 시간이 주어지면,이 memetic 다단계 알고리즘은 혁명적 인 Kahypar 구성, Hmetis 및 Patoh의 반복적 인 실행보다 더 잘 수행됩니다. 명령 줄 매개 변수 --time-limit=xxx 사용하여 최대 실행 시간 (초)을 설정할 수 있습니다. 매개 변수 --partition-evolutionary=true 진화론 적 분할을 가능하게합니다.
기존 파티션 개선
Kahypar는 직접 K-way v-cycles를 사용하여 매개 변수를 통해 지정된 기존 파티션을 개선하려고 시도합니다. --part-file=</path/to/file> . V-Cycles의 최대 수는 매개 변수 --vcycles= 를 통해 제어 할 수 있습니다.
분할 지시 된 acyclic hypergraphs
코드는 메인 리포지토리로 병합되지 않았지만, acyclic hypergraph 파티셔닝을 지원하는 포크가 있습니다. 자세한 내용은 해당 회의 간행물에서 찾을 수 있습니다.
우리는 성능 프로파일을 사용하여 Kahypar를 솔루션 품질 측면에서 다른 파티셔닝 알고리즘과 비교합니다. 세트를 위해
알고리즘 및 벤치 마크 세트
포함
인스턴스, 성능 비율
예를 들어 파티셔너 P 에 의해 계산 된 컷을 예를 들어 I는 모든 알고리즘의 최소 최소 컷 (즉,)과 관련이 있습니다.
.
성능 프로필
그런 다음 알고리즘 P는 함수에 의해 주어진다
.
연결 최적화를 위해 성능 비율은 연결 값을 사용하여 계산됩니다.
컷 값 대신. 의 가치
파티션 자 P가 최상의 솔루션을 계산 한 인스턴스의 비율에 해당하는 반면 성능 비율 일 확률입니다 요인 내에 있습니다
최상의 가능한 비율 중. 성능 프로파일은 최상의 알고리즘에 비해 각 알고리즘의 성능 만 평가할 수 있으므로
값은 알고리즘을 순위에 올리는 데 사용될 수 없습니다 (즉, 두 번째로 가장 좋은 알고리즘 등을 결정하기 위해 값.
실험 분석 에서 성능 프로파일 플롯은 각 인스턴스에 대해 발견 된 각 알고리즘 을 기반으로합니다. 또한 매개 변수를 선택합니다
모든 p , i 및
성능 비율
알고리즘 P 가 예를 들어 I , 및
주어진 시간 제한 내에 알고리즘이 솔루션을 계산할 수없는 경우 에만 . 우리의 성능 프로파일 플롯에서, x- 축의 X -Tick에 실행 가능한 솔루션에 해당하는 성능 비율이 표시되는 반면, 시간 제한 내에 분할 할 수없는 인스턴스는 아래 플롯을 종료하는 줄에 의해 암시 적으로 표시됩니다.
. 성능 비율이 크게 오른쪽으로 비워지기 때문에 성능 프로파일 플롯은 매개 변수의 다른 범위를 가진 세 개의 세그먼트로 나뉩니다. 다양한 관심 분야를 반영합니다. 첫 번째 세그먼트는 작은 값을 강조합니다 (
), 두 번째 세그먼트는 모든 인스턴스에 대한 결과를 포함합니다.
최상의 가능한 비율보다 더 나쁩니다. 마지막 세그먼트에는 모든 남은 비율, 즉 일부 알고리즘이 최고의 알고리즘보다 상당히 악화 된 인스턴스, 알고리즘이 불가분의 솔루션을 생성 한 인스턴스 및 주어진 시간 제한 내에 분할 할 수없는 인스턴스를 포함합니다.
그림에서, 우리는 Kahypar가 품질 (Patoh-Q) 및 기본 모드 (Patoh-D), K-way (Hmetis-K) 및 HMETIS 2.0 (P1)의 재귀 이등분 변형 (HMETIS-R), Algebraic 거리 기반 거친 (Zoltan-Algd), Mondriaan V.1.1.1.1.4.2.1. 알고리즘.
솔루션 품질 
달리기 시간 
우리는 모든 Kahypar 관련 간행물에 대한 추가 리소스를 제공합니다.
| Kkahypar-sea20 / rkahypar-sea20 | Sea'20 | 종이 | Tr | 슬라이드 | 실험 결과 |
|---|---|---|---|---|---|
| Kkahypar / rkahypar | - | 논문 | - | 슬라이드 | 실험 결과 |
| 카이파르 -MF / 카이파르 -R-MF | Sea'18 / jea'19 | 바다 종이 / JEA 종이 | Tr | 슬라이드 | 실험 결과 : 바다 / 제아 |
| Kahypar-e (Evohgp) | gecco'18 | 종이 | Tr | 슬라이드 | 실험 결과 |
| 카파이르 -ca | 바다 17 | 종이 | - | 슬라이드 | 실험 결과 |
| 카이파르크 | 알렌 렉스 17 | 종이 | - | 슬라이드 | 실험 결과 |
| 카이파르 -R | 알렌 렉스 16 | 종이 | Tr | 슬라이드 | 실험 결과 |
Karlsruhe Hypergraph Partitioning Framework는 다음을 요구합니다.
g++ 버전 9 이상 또는 clang 버전 11.0.3 이상과 같은 현대식 컴파일러.-DKAHYPAR_USE_MINIMAL_BOOST=ON cmake 명령에 추가하여 필요한 종속성을 자동으로 다운로드, 추출 및 빌드 할 수 있습니다. 서브 모듈을 포함하여 저장소를 복제하십시오.
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
빌드 디렉토리 만들기 : mkdir build && cd build 만듭니다
CMAKE 실행 : cmake .. -DCMAKE_BUILD_TYPE=RELEASE
실행 : make
프로젝트가 구축되는 동안 테스트가 자동으로 실행됩니다. 또한 test 대상이 제공됩니다. 엔드 투 엔드 통합 테스트는 다음과 같이 시작할 수 있습니다 : make integration_tests . 프로파일 링은 cmake 플래그를 통해 활성화 될 수 있습니다 : -DENABLE_PROFILE=ON .
독립형 프로그램은 make KaHyPar 통해 구축 할 수 있습니다. 바이너리는 다음에 위치합니다 : build/kahypar/application/ .
Kahypar에는 몇 가지 구성 매개 변수가 있습니다. 가능한 모든 매개 변수의 목록은 ./KaHyPar --help 실행하십시오. 입력 하이퍼 그래프 파일의 HMETIS 형식과 파티션 출력 파일을 사용합니다.
명령 줄 매개 변수 --quiet=1 사용하여 모든 로깅 출력을 억제 할 수 있습니다. 라이브러리 인터페이스를 사용하는 경우 해당 .ini 구성 파일에 quiet=1 추가하면 효과가 동일합니다.
우리는 2 개의 기본 프레임 워크 구성 - 하나는 재귀 적 분기 분화 ( r kahypar)와 직접 K -way 파티셔닝 ( K Kahypar)을위한 두 가지 기본 프레임 워크 구성을 제공합니다.
일반적으로 K Kahypar는 러닝 타임과 솔루션 품질 측면에서 R Kahypar보다 더 잘 수행하므로 사용하는 것이 좋습니다.
K Kahypar를 시작하려면 (연결성 -1) 목표 실행을 최적화합니다.
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar_sea20.ini
K Kahypar를 시작하려면 컷 순 목표 실행 최적화 :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/cut_kKaHyPar_sea20.ini
R Kahypar를 시작하려면 (연결성 -1) 목표 실행을 최적화합니다.
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m recursive -p ../../../config/km1_rKaHyPar_sea20.ini
R Kahypar를 시작하려면 컷 순 목표 실행을 최적화합니다.
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rKaHyPar_sea20.ini
memetic 알고리즘을 시작하려면 K Kahypar -e (연결성 -1) 목표 실행을 최적화합니다.
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar-E_sea20.ini
또한, 우리는 Alenex'16, Alenex'17, Sea'17, Sea'18, Gecco'18 및 JEA 저널 논문 및 Sebastian Schlag의 논문에 사용 된 구성에 해당하는 다양한 사전 설정을 제공합니다. 이 구성은 config/Old_Reference_Configs 폴더에 있습니다. 이러한 구성을 사용하려면 Kahypar Release 1.1.0을 확인해야합니다. 일부 기존 코드는 가장 최신 릴리스에서 제거되었으므로.
Kahypar-MF ( 유량 기반 정제 사용)를 시작하려면 (연결성 -1) 직접 K- 웨이 모드 실행을 사용하여 목표를 최적화합니다.
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_kahypar_mf_jea19.ini
Kahypar-MF를 시작하려면 ( 흐름 기반 개선 사용) 직접 K- 웨이 모드 실행을 사용하여 Cut-Net 목표 최적화 :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/old_reference_configs/cut_kahypar_mf_jea19.ini
evohgp/kahypar-e를 시작하려면 (연결성 -1) 직접 k- 웨이 모드 실행을 사용한 목표 최적화
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_gecco18.ini
구성 km1_direct_kway_gecco18.ini 는 kahypar-ca를 기반으로합니다. 그러나 Kahypar-E는 또한 흐름 기반 로컬 개선과 함께 작동합니다. JEA 간행물에서 km1_kahypar_e_mf_jea19.ini 구성이 사용되었습니다.
Kahypar-CA를 시작하려면 ( 커뮤니티 인식 조언 사용) 직접 K-way 모드 실행을 사용한 (연결성 -1) 목표 최적화 :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_sea17.ini
직접 K-way 모드 (Kahypar-K)에서 Kahypar를 시작하려면 (연결성 -1) 목표 실행을 최적화합니다.
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_alenex17.ini
재귀 이등분 모드 (Kahypar-R)에서 Kahypar를 시작하려면 Cut-Net 목표 실행 최적화 :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/old_reference_configs/cut_rb_alenex16.ini
해당 명령 줄 옵션을 사용하여 모든 사전 설정 매개 변수를 덮어 쓸 수 있습니다.
하이퍼 그래프를 만들 때 Kahypar는 입력이 실제로 올바른 하이퍼 그래프임을 확인하고 그렇지 않으면 오류를 인쇄하고 중단합니다. 이는 HGR 입력 파일, C 인터페이스 및 Python 인터페이스에 적용됩니다. 검증의 런타임 비용은 거의 모든 경우에 무시할 수 있어야합니다. 그러나 CMAKE 플래그 -DKAHYPAR_INPUT_VALIDATION=OFF 사용하여 입력 유효성 검사를 비활성화 할 수도 있습니다.
또한 경고는 치명적이지 않은 문제 (예 : 중복 핀이있는 하이퍼링)에 대해 인쇄됩니다. 치명적이지 않은 문제를 대신 하드 오류로 취급하려면 cmake 플래그 -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON 사용하십시오.
Kahypar를 라이브러리로 사용하기위한 간단한 C 스타일 인터페이스를 제공합니다. 이 인터페이스는 아직 스레드 안전이 아닙니다. 그러나 기존의 해결 방법이 있습니다. 라이브러리를 통해 제작 및 설치할 수 있습니다
make install.library다음과 같이 사용할 수 있습니다.
# include < memory >
# include < vector >
# include < iostream >
# include < libkahypar.h >
int main ( int argc, char * argv[]) {
kahypar_context_t * context = kahypar_context_new ();
kahypar_configure_context_from_file (context, " /path/to/config.ini " );
kahypar_set_seed (context, 42 );
const kahypar_hypernode_id_t num_vertices = 7 ;
const kahypar_hyperedge_id_t num_hyperedges = 4 ;
std::unique_ptr< kahypar_hyperedge_weight_t []> hyperedge_weights = std::make_unique< kahypar_hyperedge_weight_t []>( 4 );
// force the cut to contain hyperedge 0 and 2
hyperedge_weights[ 0 ] = 1 ; hyperedge_weights[ 1 ] = 1000 ;
hyperedge_weights[ 2 ] = 1 ; hyperedge_weights[ 3 ] = 1000 ;
std::unique_ptr< size_t []> hyperedge_indices = std::make_unique< size_t []>( 5 );
hyperedge_indices[ 0 ] = 0 ; hyperedge_indices[ 1 ] = 2 ;
hyperedge_indices[ 2 ] = 6 ; hyperedge_indices[ 3 ] = 9 ;
hyperedge_indices[ 4 ] = 12 ;
std::unique_ptr< kahypar_hyperedge_id_t []> hyperedges = std::make_unique< kahypar_hyperedge_id_t []>( 12 );
// hypergraph from hMetis manual page 14
hyperedges[ 0 ] = 0 ; hyperedges[ 1 ] = 2 ;
hyperedges[ 2 ] = 0 ; hyperedges[ 3 ] = 1 ;
hyperedges[ 4 ] = 3 ; hyperedges[ 5 ] = 4 ;
hyperedges[ 6 ] = 3 ; hyperedges[ 7 ] = 4 ;
hyperedges[ 8 ] = 6 ; hyperedges[ 9 ] = 2 ;
hyperedges[ 10 ] = 5 ; hyperedges[ 11 ] = 6 ;
const double imbalance = 0.03 ;
const kahypar_partition_id_t k = 2 ;
kahypar_hyperedge_weight_t objective = 0 ;
std::vector< kahypar_partition_id_t > partition (num_vertices, - 1 );
kahypar_partition (num_vertices, num_hyperedges,
imbalance, k,
/* vertex_weights */ nullptr , hyperedge_weights. get (),
hyperedge_indices. get (), hyperedges. get (),
&objective, context, partition. data ());
for ( int i = 0 ; i != num_vertices; ++i) {
std::cout << i << " : " << partition[i] << std::endl;
}
kahypar_context_free (context);
} g++ run을 사용하여 프로그램을 컴파일하려면 :
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar 참고 : 링크 중에 부스트를 찾을 수없는 경우 -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options 명령에 추가해야 할 수도 있습니다.
시스템에서 라이브러리를 제거하려면 제공된 제거 대상을 사용하십시오.
make uninstall-kahypar파이썬 인터페이스를 컴파일하려면 다음을 수행하십시오.
mkdir build && cd build 만듭니다cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 실행하십시오. 부스트가 설치되어 있지 않은 경우 run : cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON . 필요한 종속성을 자동으로 다운로드, 추출 및 구축합니다.cd python 으로 이동하십시오make 컴파일하십시오cp kahypar.so <path-to-site-packages> 사이트 패키지 디렉토리에 복사하십시오.그런 다음 Kahypar Libary를 다음과 같이 사용할 수 있습니다.
import os
import kahypar as kahypar
num_nodes = 7
num_nets = 4
hyperedge_indices = [ 0 , 2 , 6 , 9 , 12 ]
hyperedges = [ 0 , 2 , 0 , 1 , 3 , 4 , 3 , 4 , 6 , 2 , 5 , 6 ]
node_weights = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
edge_weights = [ 11 , 22 , 33 , 44 ]
k = 2
hypergraph = kahypar . Hypergraph ( num_nodes , num_nets , hyperedge_indices , hyperedges , k , edge_weights , node_weights )
context = kahypar . Context ()
context . loadINIconfiguration ( "<path/to/config>/km1_kKaHyPar_sea20.ini" )
context . setK ( k )
context . setEpsilon ( 0.03 )
kahypar . partition ( hypergraph , context )Python Library 기능에 대한 자세한 내용은 Module.cpp를 참조하십시오.
또한 사전 컴파일 된 버전을 A로 제공하며 다음을 통해 설치할 수 있습니다.
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
Jordan Jalving (@Jalving) 덕분에 Kahypar는 현재 Julia 인터페이스를 제공하며 현재 여기에서 찾을 수 있습니다 : Kahypar/Kahypar.jl.
해당 종속성은 다음을 통해 설치할 수 있습니다.
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )그런 다음 Kahypar를 사용하여 다음과 같은 과다 그래프를 분할 할 수 있습니다.
using KaHyPar
using SparseArrays
I = [ 1 , 3 , 1 , 2 , 4 , 5 , 4 , 5 , 7 , 3 , 6 , 7 ]
J = [ 1 , 1 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 ]
V = Int .( ones ( length (I)))
A = sparse (I,J,V)
h = KaHyPar . hypergraph (A)
KaHyPar . partition (h, 2 ,configuration = :edge_cut )
KaHyPar . partition (h, 2 ,configuration = :connectivity )
KaHyPar . partition (h, 2 ,configuration = joinpath ( @__DIR__ , " ../src/config/km1_kKaHyPar_sea20.ini " ))Romain Wallon은 Kahypar를위한 Java 인터페이스를 만들었습니다. 인터페이스를 빌드하고 사용하는 방법에 대한 자세한 설명은 readme를 참조하십시오.
프로젝트의 Github 문제 추적 시스템을 통해 Kahypar의 문제를보고하는 것이 좋습니다.
Kahypar는 GNU General Public License (GPLV3)에 따라 제공되는 무료 소프트웨어입니다. 자세한 내용은 복사 파일을 참조하십시오. 우리는이 프레임 워크를 자유롭게 배포하여 하이퍼 그래프 파티셔닝 도구의 사용 및 개발을 촉진합니다. 학업 환경에서 Kahypar를 사용하는 경우 적절한 서류를 인용하십시오. 상업용 라이센스에 관심이 있으시면 저에게 연락하십시오.
// Overall KaHyPar framework
@phdthesis{DBLP:phd/dnb/Schlag20,
author = {Sebastian Schlag},
title = {High-Quality Hypergraph Partitioning},
school = {Karlsruhe Institute of Technology, Germany},
year = {2020}
}
@article{10.1145/3529090,
author = {Schlag, Sebastian and
Heuer, Tobias and
Gottesb"{u}ren, Lars and
Akhremtsev, Yaroslav and
Schulz, Christian and
Sanders, Peter},
title = {High-Quality Hypergraph Partitioning},
url = {https://doi.org/10.1145/3529090},
doi = {10.1145/3529090},
journal = {ACM J. Exp. Algorithmics},
year = {2022},
month = {mar}
}
// KaHyPar-R
@inproceedings{shhmss2016alenex,
author = {Sebastian Schlag and
Vitali Henne and
Tobias Heuer and
Henning Meyerhenke and
Peter Sanders and
Christian Schulz},
title = {k-way Hypergraph Partitioning via emph{n}-Level Recursive
Bisection},
booktitle = {18th Workshop on Algorithm Engineering and Experiments, (ALENEX 2016)},
pages = {53--67},
year = {2016},
}
// KaHyPar-K
@inproceedings{ahss2017alenex,
author = {Yaroslav Akhremtsev and
Tobias Heuer and
Peter Sanders and
Sebastian Schlag},
title = {Engineering a direct emph{k}-way Hypergraph Partitioning Algorithm},
booktitle = {19th Workshop on Algorithm Engineering and Experiments, (ALENEX 2017)},
pages = {28--42},
year = {2017},
}
// KaHyPar-CA
@inproceedings{hs2017sea,
author = {Tobias Heuer and
Sebastian Schlag},
title = {Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure},
booktitle = {16th International Symposium on Experimental Algorithms, (SEA 2017)},
pages = {21:1--21:19},
year = {2017},
}
// KaHyPar-MF
@inproceedings{heuer_et_al:LIPIcs:2018:8936,
author ={Tobias Heuer and Peter Sanders and Sebastian Schlag},
title ={{Network Flow-Based Refinement for Multilevel Hypergraph Partitioning}},
booktitle ={17th International Symposium on Experimental Algorithms (SEA 2018)},
pages ={1:1--1:19},
year ={2018}
}
@article{KaHyPar-MF-JEA,
author = {Heuer, T. and Sanders, P. and Schlag, S.},
title = {Network Flow-Based Refinement for Multilevel Hypergraph Partitioning},
journal = {ACM Journal of Experimental Algorithmics (JEA)}},
volume = {24},
number = {1},
month = {09},
year = {2019},
pages = {2.3:1--2.3:36},
publisher = {ACM}
}
// KaHyPar-E (EvoHGP)
@inproceedings{Andre:2018:MMH:3205455.3205475,
author = {Robin Andre and Sebastian Schlag and Christian Schulz},
title = {Memetic Multilevel Hypergraph Partitioning},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
series = {GECCO '18},
year = {2018},
pages = {347--354},
numpages = {8}
}
// KaHyPar-SEA20 (KaHyPar-HFC)
@InProceedings{gottesbren_et_al:LIPIcs:2020:12085,
author = {Lars Gottesb{"u}ren and Michael Hamann and Sebastian Schlag and Dorothea Wagner},
title = {{Advanced Flow-Based Multilevel Hypergraph Partitioning}},
booktitle = {18th International Symposium on Experimental Algorithms (SEA)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2020}
}
Kahypar 프레임 워크에 기여하는 데 관심이 있다면 저에게 연락하거나 문제 추적 시스템에 대한 문제를 만들어보십시오.
