kahypar
v.1.3.5
Hypergraphs adalah generalisasi grafik, di mana masing -masing tepi (hiper) (juga disebut net) dapat menghubungkan lebih dari dua simpul. Masalah partisi hypergraph k -way adalah generalisasi dari masalah partisi grafik yang terkenal: partisi verteks yang diatur ke k blok disjoint dengan ukuran terikat (paling banyak 1 + ε kali ukuran blok rata -rata), sambil meminimalkan fungsi objektif yang didefinisikan pada jaring.
Dua fungsi objektif yang paling menonjol adalah metrik cut-net dan konektivitas (atau λ-1). Cut-net adalah generalisasi langsung dari tujuan yang dipotong dalam partisi grafik (yaitu, meminimalkan jumlah bobot jaring yang menghubungkan lebih dari satu blok). Metrik konektivitas juga memperhitungkan angka aktual λ dari blok yang dihubungkan oleh jaring. Dengan menjumlahkan nilai-nilai (λ-1) dari semua jaring, satu secara akurat memodelkan volume komunikasi total dari multiplikasi matriks-vektor jarang paralel dan sekali lagi mendapatkan metrik yang kembali ke tepi-potong untuk grafik polos.
Kahypar adalah kerangka partisi hypergraph bertingkat untuk mengoptimalkan cut- dan (λ- 1) -metrik. Ini mendukung pembagian rekursif dan partisi K-Way langsung . Sebagai algoritma multilevel, terdiri dari tiga fase: dalam fase kasar , hypergraph dikontil untuk mendapatkan hierarki hypergraph yang lebih kecil. Setelah menerapkan algoritma partisi awal ke hypergraph terkecil di fase kedua, kasar dibatalkan dan, pada setiap level, metode pencarian lokal digunakan untuk meningkatkan partisi yang disebabkan oleh tingkat yang lebih kasar. Kahypar menanamkan pendekatan multilevel dalam versi yang paling ekstrem, hanya menghilangkan satu titik tunggal di setiap tingkat hierarki. Dengan menggunakan pendekatan tingkat N yang sangat halus ini dikombinasikan dengan heuristik pencarian lokal yang kuat, ia menghitung solusi dengan kualitas yang sangat tinggi. Algoritma dan hasil eksperimen terperinci disajikan dalam beberapa publikasi penelitian.
Partisi Hypergraph dengan bobot blok variabel
Kahypar memiliki dukungan untuk bobot blok variabel. Jika opsi baris perintah --use-individual-part-weights=true digunakan, partisi mencoba untuk mempartisi hypergraph sehingga setiap blok VX memiliki bobot paling banyak BX, di mana BX dapat ditentukan untuk setiap blok secara individual menggunakan parameter baris perintah --part-weights= B1 B2 B3 ... Bk-1 . Karena kerangka kerja belum mendukung partisi yang sangat seimbang, batas atas harus sedikit lebih besar dari total berat semua simpul hypergraph. Perhatikan bahwa fitur ini masih eksperimental.
Partisi Hypergraph dengan simpul tetap
Partisi hypergraph dengan simpul tetap adalah variasi dari partisi hypergraph standar. Dalam masalah ini, ada kendala tambahan pada penugasan blok dari beberapa simpul, yaitu, beberapa simpul ditandatangani ke blok tertentu sebelum dipartisi dengan kondisi bahwa, setelah mempartisi sisa simpul "bebas", simpul tetap masih di blok yang ditugaskan. Parameter baris perintah --fixed / -f dapat digunakan untuk menentukan file fix dalam format file HMETIS Fix. Untuk hypergraph dengan simpul V, file fix terdiri dari garis V - satu untuk setiap simpul. Baris ke -i baik berisi -1 untuk menunjukkan bahwa simpul bebas untuk bergerak atau <part id> untuk menunjukkan bahwa simpul ini harus ditandatangani untuk memblokir <part id> . Perhatikan bahwa ID bagian mulai dari 0.
Kahypar saat ini mendukung tiga kebijakan kontraksi yang berbeda untuk dipartisi dengan simpul tetap:
free_vertex_only memungkinkan semua kontraksi di mana mitra kontraksi adalah simpul gratis , yaitu, memungkinkan kontraksi pasangan titik di mana kedua simpul itu gratis, atau satu simpul diperbaiki dan titik lainnya gratis.fixed_vertex_allowed Selain itu memungkinkan kontraksi dari dua simpul tetap asalkan keduanya ditandatangani ke blok yang sama . Berdasarkan eksperimen pendahuluan, ini saat ini adalah kebijakan default.equivalent_vertices hanya memungkinkan kontraksi pasangan simpul yang terdiri dari dua simpul bebas atau dua simpul tetap yang ditandatangani ke blok yang sama.Kerangka Evolusi (Kahypar-E)
Kahypar-E meningkatkan Kahypar dengan kerangka kerja evolusi seperti yang dijelaskan dalam publikasi GECCO'18 kami. Diberi waktu berjalan yang cukup besar, algoritma multilevel memetika ini berkinerja lebih baik daripada eksekusi berulang dari konfigurasi Kahypar non -evolusioner, hmetis, dan patoh. Parameter baris perintah --time-limit=xxx dapat digunakan untuk mengatur waktu berjalan maksimum (dalam detik). Parameter --partition-evolutionary=true memungkinkan partisi evolusi.
Meningkatkan partisi yang ada
Kahypar menggunakan siklus K-way langsung untuk mencoba meningkatkan partisi yang ada yang ditentukan melalui parameter --part-file=</path/to/file> . Jumlah maksimum V-siklus dapat dikontrol melalui parameter --vcycles= .
Mempartisi hypergraph asiklik terarah
Sementara kode belum digabungkan ke dalam repositori utama, ada garpu yang mendukung partisi hypergraph asiklik. Rincian lebih lanjut dapat ditemukan dalam publikasi konferensi yang sesuai.
Kami menggunakan profil kinerja untuk membandingkan Kahypar dengan algoritma partisi lainnya dalam hal kualitas solusi. Untuk satu set
Algoritma dan set tolok ukur
mengandung
contoh, rasio kinerja
menghubungkan potongan yang dihitung oleh partisi P misalnya I dengan potongan minimum terkecil dari semua algoritma, yaitu, yaitu
.
Profil kinerja
algoritma P kemudian diberikan oleh fungsi
.
Untuk optimasi konektivitas, rasio kinerja dihitung menggunakan nilai konektivitas
Alih -alih nilai potongan. Nilai
sesuai dengan fraksi contoh yang Partisi P menghitung solusi terbaik, sementara adalah probabilitas bahwa rasio kinerja berada dalam faktor
rasio terbaik. Perhatikan bahwa karena profil kinerja hanya memungkinkan untuk menilai kinerja masing -masing algoritma relatif terhadap algoritma terbaik ,
Nilai tidak dapat digunakan untuk memberi peringkat algoritma (yaitu, untuk menentukan algoritma mana yang merupakan yang terbaik kedua dll.).
Dalam analisis eksperimental kami, plot profil kinerja didasarkan pada solusi terbaik (yaitu, konektivitas/potong minimum ) setiap algoritma yang ditemukan untuk setiap instance. Selain itu, kami memilih parameter
untuk semua p , saya , dan
sehingga rasio kinerja
Jika dan hanya jika algoritma P menghitung solusi yang tidak layak misalnya i , dan
Jika dan hanya jika algoritma tidak dapat menghitung solusi misalnya saya dalam batas waktu yang diberikan. Dalam plot profil kinerja kami, rasio kinerja yang sesuai dengan solusi yang tidak layak akan ditampilkan pada X -Tick pada x -sumbu, sementara contoh yang tidak dapat dipartisi dalam batas waktu ditampilkan secara implisit oleh garis yang keluar dari plot di bawah ini
. Karena rasio kinerja sangat miring, plot profil kinerja dibagi menjadi tiga segmen dengan rentang yang berbeda untuk parameter untuk mencerminkan berbagai bidang yang diminati. Segmen pertama menyoroti nilai -nilai kecil (
), sedangkan segmen kedua berisi hasil untuk semua contoh yang mencapai faktor
lebih buruk dari rasio terbaik. Segmen terakhir berisi semua rasio yang tersisa, yaitu, contoh di mana beberapa algoritma berkinerja jauh lebih buruk daripada algoritma terbaik, contoh di mana algoritma menghasilkan solusi yang tidak layak, dan contoh yang tidak dapat dipartisi dalam batas waktu yang diberikan.
Dalam angka-angka tersebut, kami membandingkan Kahypar dengan Patoh dalam Kualitas (Patoh-Q) dan Mode Default (Patoh-D), K-Way (HMetis-K) dan varian biseksi rekursif (HMETIS-R) dari HMETIS 2.0 (P1), Zoltan menggunakan coarsening jarak jauh aljabar. algoritma.
Kualitas solusi 
Waktu berjalan 
Kami menyediakan sumber daya tambahan untuk semua publikasi terkait Kahypar:
| kahypar-sea20 / RKAHYPAR-SEA20 | Sea'20 | Kertas | Tr | Slide | Hasil eksperimen |
|---|---|---|---|---|---|
| kkahypar / RKAHYPAR | - | Disertasi | - | Slide | Hasil eksperimen |
| Kahypar-mf / Kahypar-R-MF | Sea'18 / JEA'19 | Kertas laut / Kertas jea | Tr | Slide | Hasil Eksperimen: Laut / Jea |
| Kahypar-E (EVOHGP) | GECCO'18 | Kertas | Tr | Slide | Hasil eksperimen |
| Kahypar-Ca | Sea'17 | Kertas | - | Slide | Hasil eksperimen |
| Kahypar-K | Alenex'17 | Kertas | - | Slide | Hasil eksperimen |
| Kahypar-r | Alenex'16 | Kertas | Tr | Slide | Hasil eksperimen |
Kerangka Partisi Hypergraph Karlsruhe membutuhkan:
g++ Versi 9 atau lebih tinggi atau clang 11.0.3 atau lebih tinggi.-DKAHYPAR_USE_MINIMAL_BOOST=ON bendera ke perintah cmake untuk mengunduh, mengekstrak, dan membangun dependensi yang diperlukan secara otomatis. Klon Repositori termasuk Submodules:
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
Buat direktori build: mkdir build && cd build
Jalankan cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
Jalankan Make: make
Tes dieksekusi secara otomatis saat proyek dibangun. Selain itu target test disediakan. Tes integrasi end-to-end dapat dimulai dengan: make integration_tests . Profil dapat diaktifkan melalui CMake Flag: -DENABLE_PROFILE=ON .
Program mandiri dapat dibangun melalui make KaHyPar . Biner akan berlokasi di: build/kahypar/application/ .
Kahypar memiliki beberapa parameter konfigurasi. Untuk daftar semua parameter yang mungkin, silakan jalankan: ./KaHyPar --help . Kami menggunakan format HMETIS untuk file hypergraph input serta file output partisi.
Parameter baris perintah --quiet=1 dapat digunakan untuk menekan semua output logging. Jika Anda menggunakan antarmuka perpustakaan, menambahkan quiet=1 ke file konfigurasi .ini yang sesuai memiliki efek yang sama.
Kami menyediakan dua konfigurasi kerangka kerja default - satu untuk bipartisi rekursif ( R Kahypar) dan satu untuk partisi K -Way langsung ( K Kahypar).
Secara umum, kami sarankan menggunakan K Kahypar karena berkinerja lebih baik daripada R Kahypar dalam hal waktu berjalan dan kualitas solusi.
Untuk memulai K Kahypar mengoptimalkan (konektivitas - 1) Objective Run:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar_sea20.ini
Untuk memulai K Kahypar mengoptimalkan Run Objective Cut Net :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/cut_kKaHyPar_sea20.ini
Untuk memulai R Kahypar mengoptimalkan (konektivitas - 1) Run Objective:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m recursive -p ../../../config/km1_rKaHyPar_sea20.ini
Untuk memulai R Kahypar mengoptimalkan Run Objective Cut Net :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rKaHyPar_sea20.ini
Untuk memulai algoritma memetika k kahypar -e mengoptimalkan (konektivitas - 1) menjalankan objektif:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar-E_sea20.ini
Selain itu, kami menyediakan preset berbeda yang sesuai dengan konfigurasi yang digunakan dalam publikasi di Alenex'16, Alenex'17, Sea'17, Sea'18, Gecco'18, serta dalam kertas Journal JEA kami dan dalam disertasi Sebastian Schlag. Konfigurasi ini terletak di folder config/old_reference_configs. Untuk menggunakan konfigurasi ini, Anda harus memeriksa rilis Kahypar 1.1.0, karena beberapa kode lama telah dihapus dalam rilis terkini.
Untuk memulai Kahypar-MF (menggunakan penyempurnaan berbasis aliran ) mengoptimalkan objektif (konektivitas-1) menggunakan mode K-Way langsung yang dijalankan:
./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
Untuk memulai Kahypar-MF (menggunakan penyempurnaan berbasis aliran ) mengoptimalkan tujuan cut-net menggunakan mode k-way langsung:
./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
Untuk memulai evohgp/kahypar-e mengoptimalkan tujuan (konektivitas-1) menggunakan mode k-way langsung
./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
Perhatikan bahwa konfigurasi km1_direct_kway_gecco18.ini didasarkan pada kahypar-ca. Namun, Kahypar-E juga bekerja dengan perbaikan lokal berbasis aliran. Dalam publikasi JEA kami, konfigurasi km1_kahypar_e_mf_jea19.ini digunakan.
Untuk memulai Kahypar-CA (menggunakan Community-Aware Roarsening ) mengoptimalkan (konektivitas-1) tujuan menggunakan mode K-Way langsung menjalankan:
./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
Untuk memulai Kahypar dalam mode K-Way langsung (Kahypar-K) mengoptimalkan (1) Objective Run:
./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
Untuk memulai Kahypar dalam mode biseksi rekursif (kahypar-r) mengoptimalkan run tujuan 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
Semua parameter preset dapat ditimpa dengan menggunakan opsi baris perintah yang sesuai.
Saat membuat hypergraph, Kahypar memvalidasi bahwa input sebenarnya adalah hypergraph yang benar, jika tidak mencetak kesalahan dan dibatalkan. Ini berlaku untuk file input HGR, antarmuka C dan antarmuka Python. Biaya runtime dari validasi harus diabaikan di hampir semua kasus. Namun, validasi input juga dapat dinonaktifkan menggunakan flag CMake -DKAHYPAR_INPUT_VALIDATION=OFF .
Selain itu, peringatan dicetak untuk masalah non-fatal (misalnya hyperedges dengan pin duplikat). Untuk memperlakukan masalah non -fatal sebagai kesalahan keras sebagai gantinya, gunakan bendera CMake -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON .
Kami menyediakan antarmuka gaya-C sederhana untuk menggunakan Kahypar sebagai perpustakaan. Perhatikan bahwa antarmuka ini belum aman. Namun ada beberapa solusi yang ada. Perpustakaan dapat dibangun dan diinstal melalui
make install.librarydan dapat digunakan seperti ini:
# 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);
} Untuk mengkompilasi program menggunakan g++ Run:
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar Catatan: Jika Boost tidak ditemukan selama tautan, Anda mungkin perlu menambahkan -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options ke perintah.
Untuk menghapus perpustakaan dari sistem Anda, gunakan target uninstall yang disediakan:
make uninstall-kahyparUntuk mengkompilasi antarmuka Python, lakukan hal berikut:
mkdir build && cd buildcmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 . Jika Anda tidak memiliki boost diinstal, jalankan: cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON . Ini akan mengunduh, mengekstrak, dan membangun dependensi yang diperlukan secara otomatis.cd pythonmakecp kahypar.so <path-to-site-packages>Setelah itu Anda dapat menggunakan Kahypar Libary seperti ini:
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 )Untuk informasi lebih lanjut tentang fungsionalitas perpustakaan Python, silakan lihat: Module.cpp
Kami juga memberikan versi yang dikompilasi sebagai A, yang dapat diinstal melalui:
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
Terima kasih kepada Jordan Jalving (@jalving) Kahypar sekarang juga menawarkan antarmuka Julia, yang saat ini dapat ditemukan di sini: kahypar/kahypar.jl.
Ketergantungan yang sesuai dapat diinstal melalui:
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )Setelah itu, Anda dapat menggunakan Kahypar untuk mempartisi hypergraph Anda seperti ini:
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 telah menciptakan antarmuka Java untuk Kahypar. Silakan merujuk ke ReadMe untuk deskripsi terperinci tentang cara membangun dan menggunakan antarmuka.
Kami mendorong Anda untuk melaporkan masalah apa pun dengan Kahypar melalui sistem pelacakan masalah GitHub proyek.
Kahypar adalah perangkat lunak gratis yang disediakan di bawah Lisensi Publik Umum GNU (GPLV3). Untuk informasi lebih lanjut, lihat file salinan. Kami mendistribusikan kerangka kerja ini secara bebas untuk menumbuhkan penggunaan dan pengembangan alat partisi hypergraph. Jika Anda menggunakan Kahypar dalam suasana akademik, silakan mengutip kertas yang sesuai. Jika Anda tertarik dengan lisensi komersial, silakan hubungi saya.
// 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}
}
Jika Anda tertarik untuk berkontribusi pada kerangka kerja Kahypar, jangan ragu untuk menghubungi saya atau membuat masalah pada sistem pelacakan masalah.
