kahypar
v.1.3.5
Les hypergraphes sont une généralisation de graphiques, où chaque bord (hyper) (également appelé net) peut connecter plus de deux sommets. Le problème de partitionnement hypergraphe K -Way est la généralisation du problème de partitionnement du graphique bien connu: partitionner le sommet réglé dans k blocs disjoints de taille limitée (au plus 1 + ε fois la taille moyenne du bloc), tout en minimisant une fonction objective définie sur les filets.
Les deux fonctions objectives les plus importantes sont le réseau coupé et la connectivité (ou λ - 1). Cut-Net est une généralisation simple de l'objectif de coupe de bord dans le partitionnement du graphique (c'est-à-dire, minimisant la somme des poids des filets qui se connectent plus d'un bloc). La métrique de connectivité prend également en compte le nombre réel λ de blocs connectés par un filet. En additionnant les valeurs (λ - 1) de tous les filets, on modélise avec précision le volume de communication total de la multiplication parallèle de la matrice-vecteur et obtient une fois de plus une métrique qui revient à la coupe de bord pour les graphiques simples.
Kahypar est un cadre de partitionnement hypergraphe à plusieurs niveaux pour optimiser la coupe et le métrique (λ - 1). Il prend en charge à la fois la bissection récursive et le partitionnement direct en K. En tant qu'algorithme à plusieurs niveaux, il se compose de trois phases: dans la phase de grossissement , l'hypergraphe est grossiré pour obtenir une hiérarchie d'hypergraphes plus petits. Après avoir appliqué un algorithme de partitionnement initial au plus petit hypergraphe de la deuxième phase, le grossissement est annulé et, à chaque niveau, une méthode de recherche locale est utilisée pour améliorer la partition induite par le niveau plus grossier. Kahypar instancie l'approche à plusieurs niveaux dans sa version la plus extrême, ne supprimant qu'un seul sommet à tous les niveaux de la hiérarchie. En utilisant cette approche de niveau N très fin combinée à une forte heuristique de recherche locale, il calcule des solutions de très haute qualité. Ses algorithmes et ses résultats expérimentaux détaillés sont présentés dans plusieurs publications de recherche.
Partionnement hypergraphe avec des poids de bloc variables
Kahypar supporte des poids de bloc variables. Si l'option de ligne de commande --use-individual-part-weights=true est utilisée, le partitionnaire essaie de partitionner l'hypergraphe de telle sorte que chaque bloc VX ait un poids de la plupart BX, où BX peut être spécifié pour chaque bloc individuellement en utilisant le paramètre de ligne de commande --part-weights= B1 B2 B3 ... Bk-1 . Étant donné que le cadre ne prend pas encore en charge le partitionnement parfaitement équilibré, les limites supérieures doivent être légèrement plus grandes que le poids total de tous les sommets de l'hypergraphe. Notez que cette fonctionnalité est toujours expérimentale.
Partionnement hypergraphe avec des sommets fixes
Le partitionnement hypergraphe avec des sommets fixes est une variation du partitionnement hypergraphe standard. Dans ce problème, il y a une contrainte supplémentaire sur l'attribution de blocs de certains sommets, c'est-à-dire que certains sommets sont pré-signés sur des blocs spécifiques avant de partitionner avec la condition qu'après partitionner les sommets «gratuits» restants, les sommets fixes sont toujours dans le bloc à qui ils ont été attribués. Le paramètre de ligne de commande --fixed / -f peut être utilisé pour spécifier un fichier de correctif dans le format de fichier de correction HMETIS. Pour un hypergraphe avec des sommets V, le fichier FIX se compose de lignes V - une pour chaque sommet. La ligne i th contient -1 pour indiquer que le sommet est libre de se déplacer ou <part id> pour indiquer que ce sommet doit être pré-signé pour bloquer <part id> . Notez que les ID de pièce commencent à partir de 0.
Kahypar prend actuellement en charge trois politiques de contraction différentes pour le partitionnement avec des sommets fixes:
free_vertex_only permet toutes les contractions dans lesquelles le partenaire de contraction est un sommet libre , c'est-à-dire qu'il permet les contractions de paires de sommets où les deux sommets sont libres, ou un sommet est fixe et l'autre sommet est gratuit.fixed_vertex_allowed Permet en outre les contractions de deux sommets fixes à condition que les deux soient pré-signés au même bloc. Sur la base d'expériences préliminaires, il s'agit actuellement de la politique par défaut.equivalent_vertices permet uniquement des contractions de paires de sommets qui se composent de deux sommets libres ou de deux sommets fixes pré-sidés au même bloc.Cadre évolutif (Kahypar-E)
Kahypar-E améliore Kahypar avec un cadre évolutif comme décrit dans notre publication Gecco'18. Compte tenu d'une quantité assez importante de temps d'exécution, cet algorithme à plusieurs niveaux mémétique fonctionne mieux que les exécutions répétées de configurations Kahypar non -volutionnaires, Hmetis et Patoh. Le paramètre de ligne de commande --time-limit=xxx peut être utilisé pour définir le temps d'exécution maximal (en secondes). Paramètre --partition-evolutionary=true permet le partitionnement évolutif.
Amélioration des partitions existantes
Kahypar utilise des cycles V directs en K pour essayer d'améliorer une partition existante spécifiée via le paramètre --part-file=</path/to/file> . Le nombre maximum de V-cycles peut être contrôlé via le paramètre --vcycles= .
Partitionnement des hypergraphes acycliques orientés
Bien que le code n'ait pas encore été fusionné dans le référentiel principal, il existe une fourche qui prend en charge le partitionnement hypergraphe acyclique. Plus de détails peuvent être trouvés dans la publication de conférence correspondante.
Nous utilisons les profils de performance pour comparer le kahypar à d'autres algorithmes de partitionnement en termes de qualité de solution. Pour un ensemble de
algorithmes et un ensemble de référence
contenant
instances, le rapport de performance
Relate la coupe calculée par le partitionnaire P par exemple I à la plus petite coupe minimale de tous les algorithmes, c'est-à-dire
.
Le profil de performance
de l'algorithme p est alors donné par la fonction
.
Pour l'optimisation de la connectivité, les rapports de performance sont calculés à l'aide des valeurs de connectivité
au lieu des valeurs de coupe. La valeur de
correspond à la fraction des instances pour lesquelles le partitionnaire P a calculé la meilleure solution, tandis que est la probabilité qu'un rapport de performance est à un facteur de
du meilleur rapport possible. Notez que puisque les profils de performance permettent d'évaluer uniquement les performances de chaque algorithme par rapport au meilleur algorithme, le
Les valeurs ne peuvent pas être utilisées pour classer les algorithmes (c'est-à-dire pour déterminer quel algorithme est le deuxième meilleur, etc.).
Dans notre analyse expérimentale, les tracés de profil de performance sont basés sur les meilleures solutions (c.-à-d. Connectivité minimale / coupe) chaque algorithme trouvé pour chaque instance. De plus, nous choisissons les paramètres
Pour tous P , moi et
tel qu'un rapport de performance
Si et seulement si l'algorithme P a calculé une solution irréalisable par exemple i , et
Si et seulement si l'algorithme ne pouvait pas calculer une solution par exemple I dans le délai donné. Dans nos tracés de profil de performance, les rapports de performance correspondant aux solutions irréalisables seront affichés sur le bicle x sur l'axe x , tandis que les instances qui n'ont pas pu être partitionnées dans le délai sont représentées implicitement par une ligne qui quitte le tracé ci-dessous
. Étant donné que les ratios de performance sont fortement asymétriques, les tracés de profil de performance sont divisés en trois segments avec différentes gammes pour le paramètre refléter divers domaines d'intérêt. Le premier segment met en évidence de petites valeurs (
), tandis que le deuxième segment contient des résultats pour toutes les instances qui sont jusqu'à un facteur de
Pire que le meilleur rapport possible. Le dernier segment contient tous les ratios restants, c'est-à-dire, des instances pour lesquelles certains algorithmes ont effectué beaucoup plus pire que le meilleur algorithme, des instances pour lesquelles les algorithmes ont produit des solutions infassibles et des instances qui ne pouvaient pas être partitionnées dans le délai donné.
In the figures, we compare KaHyPar with PaToH in quality (PaToH-Q) and default mode (PaToH-D), the k-way (hMETIS-K) and the recursive bisection variant (hMETIS-R) of hMETIS 2.0 (p1), Zoltan using algebraic distance-based coarsening (Zoltan-AlgD), Mondriaan v.4.2.1 and the recently published HYPE algorithme.
Qualité de la solution 
Temps de course 
Nous fournissons des ressources supplémentaires pour toutes les publications liées à Kahypar:
| Kkahypar-Sea20 / RKAHYPAR-SEA20 | Sea'20 | Papier | Tr | Diapositives | Résultats expérimentaux |
|---|---|---|---|---|---|
| kkahypar / rkahypar | - | Thèse | - | Diapositives | Résultats expérimentaux |
| Kahypar-mf / Kahypar-r-mf | Sea'18 / Jea'19 | Papier de mer / Papier en Jea | Tr | Diapositives | Résultats expérimentaux: Mer / Jea |
| Kahypar-e (evohgp) | Gecco'18 | Papier | Tr | Diapositives | Résultats expérimentaux |
| Kahypar-ca | SEA'17 | Papier | - | Diapositives | Résultats expérimentaux |
| Kahypar-k | Alenex'17 | Papier | - | Diapositives | Résultats expérimentaux |
| Kahypar-r | Alenex'16 | Papier | Tr | Diapositives | Résultats expérimentaux |
Le cadre de partitionnement hypergraphe de Karlsruhe nécessite:
g++ version 9 ou supérieur ou clang version 11.0.3 ou plus.-DKAHYPAR_USE_MINIMAL_BOOST=ON l'indicateur à la commande cmake pour télécharger, extraire et construire les dépendances nécessaires automatiquement. Clone le référentiel, y compris les sous-modules:
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
Créer un répertoire de construction: mkdir build && cd build
Exécuter cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
Run Make: make
Les tests sont automatiquement exécutés pendant la construction du projet. De plus, une cible test est fournie. Les tests d'intégration de bout en bout peuvent être lancés avec: make integration_tests . Le profilage peut être activé via un drapeau cmake: -DENABLE_PROFILE=ON .
Le programme autonome peut être construit via make KaHyPar . Le binaire sera situé à: build/kahypar/application/ .
Kahypar a plusieurs paramètres de configuration. Pour une liste de tous les paramètres possibles, veuillez exécuter: ./KaHyPar --help . Nous utilisons le format HMETIS pour le fichier Hypergraph d'entrée ainsi que le fichier de sortie de partition.
Le paramètre de ligne de commande --quiet=1 peut être utilisé pour supprimer toutes les sorties de journalisation. Si vous utilisez les interfaces de la bibliothèque, l'ajout quiet=1 au fichier de configuration .ini correspondant a le même effet.
Nous fournissons deux configurations de framework par défaut - une pour le bipartitionning récursive ( R Kahypar) et une pour le partitionnement direct de K-Way ( K Kahypar).
En général, nous vous recommandons d'utiliser K Kahypar car il fonctionne mieux que R Kahypar en termes de temps d'exécution et de qualité de la solution.
Pour démarrer K Kahypar Optimisation de la (connectivité - 1) Run objectif:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar_sea20.ini
Pour démarrer K Kahypar, optimiser l'exécution de l'objectif du net :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/cut_kKaHyPar_sea20.ini
Pour démarrer R Kahypar Optimisation de la (connectivité - 1) Run objectif:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m recursive -p ../../../config/km1_rKaHyPar_sea20.ini
Pour démarrer R Kahypar, optimiser l'exécution de l'objectif du net :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rKaHyPar_sea20.ini
Pour démarrer l'algorithme mémétique K Kahypar-E Optimisation de la (connectivité - 1) RUN OBJECTIF:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar-E_sea20.ini
De plus, nous fournissons différents préréglages qui correspondent aux configurations utilisées dans les publications d'Alenex'16, Alenex'17, SEA'17, SEA'18, Gecco'18, ainsi que dans notre document de journal Jea et dans la dissertation de Sebastian Schlag. Ces configurations se trouvent dans le dossier config / old_reference_configs. Afin d'utiliser ces configurations, vous devez vérifier la version 1.1.0 de Kahypar, car un ancien code a été supprimé dans la version la plus récente.
Pour démarrer Kahypar-MF (en utilisant le raffinement basé sur le flux ) Optimisation de l'objectif (Connectivité - 1) à l'aide du mode K-Way Direct K-WAY:
./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
Pour démarrer Kahypar-MF (en utilisant le raffinement basé sur le débit ) Optimisation de l'objectif de coupe de coupe à l'aide du mode direct K-Way Run:
./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
Pour démarrer EVOHGP / KAHYPAR-E OPTIMIZER L'OBJECTIF (CONNECTIVITÉ - 1) OBJECTIF À l'aide du mode K-WAY DIRECT
./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
Notez que la configuration km1_direct_kway_gecco18.ini est basée sur Kahypar-CA. Cependant, Kahypar-E travaille également avec les améliorations locales basées sur les flux. Dans notre publication JEA, la configuration km1_kahypar_e_mf_jea19.ini a été utilisée.
Pour démarrer Kahypar-CA (en utilisant le grossissement de la communauté ) Optimisation de l'objectif (Connectivité - 1) à l'aide du mode K-Way Direct 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_sea17.ini
Pour démarrer Kahypar en mode K-Way Direct (Kahypar-K) Optimisation de la (Connectivité - 1) RUN OBJECTIF:
./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
Pour démarrer le kahypar en mode de bissection récursif (Kahypar-R) Optimisation de l'exécution de l'objectif de coupe:
./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
Tous les paramètres prédéfinis peuvent être écrasés en utilisant les options de ligne de commande correspondantes.
Lors de la création d'un hypergraphe, Kahypar valide que l'entrée est en fait un hypergraphe correct, sinon imprimer une erreur et abandonner. Cela s'applique aux fichiers d'entrée HGR, à l'interface C et à l'interface Python. Le coût d'exécution de la validation devrait être négligeable dans presque tous les cas. Cependant, la validation d'entrée peut également être désactivée à l'aide de l'indicateur cmake -DKAHYPAR_INPUT_VALIDATION=OFF .
De plus, les avertissements sont imprimés pour des problèmes non mortels (par exemple, les hyperedges avec des épingles en double). Pour traiter les problèmes non mortels comme des erreurs difficiles à la place, utilisez le drapeau cmake -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON .
Nous fournissons une interface de style C simple pour utiliser Kahypar comme bibliothèque. Notez que cette interface n'est pas encore filée. Cependant, il existe des solutions de contournement existantes. La bibliothèque peut être construite et installée via
make install.libraryet peut être utilisé comme ceci:
# 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);
} Pour compiler le programme à l'aide de g++ Run:
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar Remarque: Si Boost n'est pas trouvé lors de la liaison, vous devrez peut-être ajouter -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options à la commande.
Pour supprimer la bibliothèque de votre système, utilisez la cible de désinstallation fournie:
make uninstall-kahyparPour compiler l'interface Python, procédez comme suit:
mkdir build && cd buildcmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 . Si vous n'avez pas l'installation de boost, exécutez: cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON . Cela téléchargera, extraire et construire automatiquement les dépendances nécessaires.cd pythonmakecp kahypar.so <path-to-site-packages>Après cela, vous pouvez utiliser le kahypar libary comme ceci:
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 )Pour plus d'informations sur la fonctionnalité de la bibliothèque Python, veuillez consulter: module.cpp
Nous fournissons également une version précompilée en tant que A, qui peut être installée via:
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
Merci à Jordan Jalving (@Jalving) Kahypar propose désormais également une interface Julia, qui peut actuellement être trouvée ici: Kahypar / Kahypar.jl.
La dépendance correspondante peut être installée via:
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )Après cela, vous pouvez utiliser Kahypar pour partitionner vos hypergraphes comme ceci:
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 a créé une interface Java pour Kahypar. Veuillez vous référer à la lecture pour une description détaillée de la façon de créer et d'utiliser l'interface.
Nous vous encourageons à signaler tout problème avec Kahypar via le système de suivi des problèmes GitHub du projet.
Kahypar est un logiciel libre fourni en vertu de la licence publique générale GNU (GPLV3). Pour plus d'informations, consultez le fichier de copie. Nous distribuons librement ce cadre pour favoriser l'utilisation et le développement d'outils de partitionnement hypergraphe. Si vous utilisez Kahypar dans un cadre académique, veuillez citer les papiers appropriés. Si vous êtes intéressé par une licence commerciale, veuillez me contacter.
// 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}
}
Si vous souhaitez contribuer au cadre de Kahypar, n'hésitez pas à me contacter ou à créer un problème sur le système de suivi des problèmes.
