kahypar
v.1.3.5
Los hipérgicos son una generalización de gráficos, donde cada borde (hiper) (también llamado NET) puede conectar más de dos vértices. El problema de división del hipergrafio K -Way es la generalización del problema de partición gráfica bien conocido: divide el vértice establecido en k bloques de disjunto de k del tamaño limitado (como máximo 1 + ε veces el tamaño promedio del bloque), al tiempo que minimiza una función objetivo definida en las redes.
Las dos funciones objetivas más destacadas son las métricas de conectividad y conectividad (o λ-1). Cut-Net es una generalización directa del objetivo de corte de borde en la partición gráfica (es decir, minimizando la suma de los pesos de esas redes que conectan más de un bloque). La métrica de conectividad además tiene en cuenta el número real λ de bloques conectados por una red. Al sumar los valores (λ-1) de todas las redes, uno modela con precisión el volumen de comunicación total de la multiplicación paralela de vector de matriz escasa y una vez más obtiene una métrica que vuelve a cortar bordes para gráficos simples.
Kahypar es un marco de división de hipergrafías multinivel para optimizar el corte y el (λ- 1)-metric. Admite tanto la bisección recursiva como la partición directa de K-Way . Como algoritmo multinivel, consiste en tres fases: en la fase de engrosamiento , el hipergrafo se engrasa para obtener una jerarquía de hipergrafos más pequeños. Después de aplicar un algoritmo de partición inicial al hipergrafo más pequeño en la segunda fase, el engrosamiento se deshace y, en cada nivel, se utiliza un método de búsqueda local para mejorar la partición inducida por el nivel más grueso. Kahypar instancia el enfoque multinivel en su versión más extrema, eliminando solo un vértice en todos los niveles de la jerarquía. Al utilizar este enfoque de nivel N de grano muy fino combinado con una fuerte heurística de búsqueda local, calcula soluciones de muy alta calidad. Sus algoritmos y resultados experimentales detallados se presentan en varias publicaciones de investigación.
Amplio de hipergrafías con pesos de bloque variables
Kahypar tiene soporte para pesos de bloque variables. Si se usa la opción Línea de comando --use-individual-part-weights=true , el Parcionador intenta dividir el hipergrafio de tal manera que cada bloque VX tiene un peso de la mayoría de BX, donde BX se puede especificar para cada bloque utilizando individualmente el parámetro de línea de comandos --part-weights= B1 B2 B3 ... Bk-1 . Dado que el marco aún no es compatible con la partición perfectamente equilibrada, los límites superiores deben ser ligeramente más grandes que el peso total de todos los vértices del hipergrafo. Tenga en cuenta que esta característica sigue siendo experimental.
Amplio de hipergrafías con vértices fijos
El particionamiento de hipergrafio con vértices fijos es una variación de la división de hipergrafio estándar. En este problema, hay una restricción adicional en la asignación de bloques de algunos vértices, es decir, algunos vértices están preasignados a bloques específicos antes de la partición con la condición de que, después de dividir los vértices "libres" restantes, los vértices fijos todavía están en el bloque al que fueron asignados. El parámetro de línea de comandos --fixed / -f se puede usar para especificar un archivo corrigido en formato de archivo fijo hmetis. Para un hipergrafo con vértices V, el archivo Fix consiste en líneas V, una para cada vértice. La línea I TH contiene -1 para indicar que el vértice es libre de moverse o <part id> para indicar que este vértice debe ser preasignado para bloquear <part id> . Tenga en cuenta que las ID de la parte comienzan desde 0.
Kahypo actualmente admite tres políticas de contracción diferentes para la partición con vértices fijos:
free_vertex_only permite todas las contracciones en las que el socio de contracción es un vértice libre , es decir, permite contracciones de pares de vértices donde ambos vértices son libres o un vértice es fijo y el otro vértice está libre.fixed_vertex_allowed adicionalmente permite contracciones de dos vértices fijos siempre que ambos estén preasignados al mismo bloque. Basado en experimentos preliminares, esta es actualmente la política predeterminada.equivalent_vertices solo permite contracciones de pares de vértices que consisten en dos vértices libres o dos vértices fijos preasignados al mismo bloque.Marco evolutivo (Kahypo-e)
Kahypo-E mejora Kahypar con un marco evolutivo como se describe en nuestra publicación GECCO'18. Dado una cantidad bastante grande de tiempo de ejecución, este algoritmo Memetic Multrevel funciona mejor que las ejecuciones repetidas de configuraciones de Kahypo novolutivas, Hmetis y Patoh. El parámetro de línea de comando --time-limit=xxx se puede usar para establecer el tiempo de ejecución máximo (en segundos). Parámetro --partition-evolutionary=true permite la partición evolutiva.
Mejora de las particiones existentes
Kahypar utiliza ciclos V Direct K-Way para tratar de mejorar una partición existente especificada a través del parámetro --part-file=</path/to/file> . El número máximo de ciclos V se puede controlar a través del parámetro --vcycles= .
Partitionamiento dirigido a hipergrafos acíclicos
Si bien el código aún no se ha fusionado en el repositorio principal, existe una bifurcación que admite la división acíclica de hipergrafes. Se pueden encontrar más detalles en la publicación de la Conferencia correspondiente.
Utilizamos los perfiles de rendimiento para comparar Kahypar con otros algoritmos de partición en términos de calidad de solución. Para un conjunto de
algoritmos y un conjunto de referencia
que contiene
instancias, la relación de rendimiento
relata el corte calculado por el particionador P, por ejemplo , con el corte mínimo más pequeño de todos los algoritmos, es decir,
.
El perfil de rendimiento
del algoritmo P viene entonces dada por la función
.
Para la optimización de conectividad, las relaciones de rendimiento se calculan utilizando los valores de conectividad
en lugar de los valores de corte. El valor de
corresponde a la fracción de instancias para las cuales el particionador P calculó la mejor solución, mientras que es la probabilidad de que una relación de rendimiento está dentro de un factor de
de la mejor relación posible. Tenga en cuenta que dado que los perfiles de rendimiento solo permiten evaluar el rendimiento de cada algoritmo en relación con el mejor algoritmo, el
Los valores no se pueden usar para clasificar los algoritmos (es decir, para determinar qué algoritmo es el segundo mejor, etc.).
En nuestro análisis experimental, los gráficos de perfil de rendimiento se basan en las mejores soluciones (es decir, conectividad/corte mínimo ) cada algoritmo que se encuentra para cada instancia. Además, elegimos parámetros
para todos p , yo y
tal que una relación de rendimiento
Si y solo si el algoritmo P calculó una solución infalible, por ejemplo, I , y
Si y solo si el algoritmo no pudiera calcular una solución, por ejemplo, I dentro del límite de tiempo dado. En nuestras gráficas de perfil de rendimiento, las relaciones de rendimiento correspondientes a soluciones inviables se mostrarán en la tarea X en el eje x , mientras que las instancias que no podrían dividirse dentro del límite de tiempo se muestran implícitamente por una línea que sale de la gráfica a continuación
. Dado que las relaciones de rendimiento son muy sesgadas a la derecha, las gráficas de perfil de rendimiento se dividen en tres segmentos con diferentes rangos para el parámetro para reflejar varias áreas de interés. El primer segmento destaca valores pequeños (
), mientras que el segundo segmento contiene resultados para todas las instancias que están hasta un factor de
peor que la mejor relación posible. El último segmento contiene todas las relaciones restantes, es decir, casos para las cuales algunos algoritmos tuvieron un rendimiento considerable que el mejor algoritmo, casos para los que los algoritmos produjeron soluciones inviables e instancias que no podían dividirse dentro del límite de tiempo dado.
En las cifras, comparamos Kahypar con Patoh en calidad (Patoh-Q) y modo predeterminado (Patoh-D), K-Way (HMETIS-K) y la variante de bisección recursiva (HMETIS-R) de HMETIS 2.0 (P1), Zoltan utilizando algebraico a distancia (Zolte-ALGD), Mondría V.4.
Calidad de la solución 
Tiempo de ejecución 
Proporcionamos recursos adicionales para todas las publicaciones relacionadas con Kahypo:
| KKAHYPAR-SEA20 / rkahypar-sea20 | Sea'20 | Papel | TR | Toboganes | Resultados experimentales |
|---|---|---|---|---|---|
| KKAHYPAR / rkahypar | - | Disertación | - | Toboganes | Resultados experimentales |
| Kahypo-MF / Kahypo-R-MF | SEA'18 / Jea'19 | Papel marino / Papel jea | TR | Toboganes | Resultados experimentales: Mar / jea |
| Kahypo-e (EVOHGP) | Gecco'18 | Papel | TR | Toboganes | Resultados experimentales |
| Kahypar-c | SEA'17 | Papel | - | Toboganes | Resultados experimentales |
| Kahypar-k | Alenex'17 | Papel | - | Toboganes | Resultados experimentales |
| Kahypo-R | Alenex'16 | Papel | TR | Toboganes | Resultados experimentales |
El marco de división de Hypergraph Karlsruhe requiere:
g++ versión 9 o superior o clang versión 11.0.3 o superior.-DKAHYPAR_USE_MINIMAL_BOOST=ON FLAG al comando cmake para descargar, extraer y construir las dependencias necesarias automáticamente. Clon el repositorio que incluye submódulos:
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
Cree un directorio de compilación: mkdir build && cd build
Ejecutar cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
Run Make: make
Las pruebas se ejecutan automáticamente mientras se construye el proyecto. Además, se proporciona un objetivo test . Las pruebas de integración de extremo a extremo se pueden comenzar con: make integration_tests . El perfil se puede habilitar a través del indicador Cmake: -DENABLE_PROFILE=ON .
El programa independiente se puede construir a través de make KaHyPar . El binario se ubicará en: build/kahypar/application/ .
Kahypar tiene varios parámetros de configuración. Para obtener una lista de todos los parámetros posibles, ejecute: ./KaHyPar --help . Utilizamos el formato HMETIS para el archivo de hipergrafio de entrada, así como el archivo de salida de partición.
El parámetro de línea de comando --quiet=1 se puede usar para suprimir toda la salida de registro. Si está utilizando las interfaces de la biblioteca, agregar quiet=1 al archivo de configuración .ini correspondiente tiene el mismo efecto.
Proporcionamos dos configuraciones de marco predeterminadas: una para bipartición recursiva ( R Kahypar) y otra para división directa de K -Way ( K Kahypar).
En general, recomendamos usar K Kahypo, ya que funciona mejor que R Kahypar en términos de tiempo de ejecución y calidad de solución.
Para iniciar K Kahypar, optimización de (conectividad - 1) Ejecutar el objetivo:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar_sea20.ini
Para iniciar K Kahypo optimizando la ejecución del objetivo neto de corte :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/cut_kKaHyPar_sea20.ini
Para iniciar R Kahypo optimizando la ejecución del objetivo (conectividad - 1) :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m recursive -p ../../../config/km1_rKaHyPar_sea20.ini
Para iniciar R Kahypo optimizando la ejecución del objetivo neto de corte :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rKaHyPar_sea20.ini
Para iniciar el algoritmo memético K kahypar -e optimizando (conectividad - 1) ejecución del objetivo:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar-E_sea20.ini
Además, proporcionamos diferentes presets que corresponden a las configuraciones utilizadas en las publicaciones en Alenex'16, Alenex'17, SEA'17, SEA'18, GECCO'18, así como en nuestro documento de JEA Journal y en la disertación de Sebastian Schlag. Estas configuraciones se encuentran en la carpeta config/old_reference_configs. Para utilizar estas configuraciones, debe pagar Kahypo Release 1.1.0, ya que algún código anterior se ha eliminado en la versión más actual.
Para iniciar Kahypar-MF (usando el refinamiento basado en el flujo ) optimizando el objetivo (conectividad-1) utilizando el modo Direct K-Way Run:
./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
Para iniciar Kahypar-MF (usando el refinamiento basado en el flujo ) optimizando el objetivo de red de corte utilizando el modo 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
Para iniciar EVOHGP/KAHYPAR-E optimizando el objetivo (conectividad-1) utilizando el modo Director K-Way 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_gecco18.ini
Tenga en cuenta que la configuración km1_direct_kway_gecco18.ini se basa en Kahypar-Ca. Sin embargo, Kahypo-E también trabaja con mejoras locales basadas en el flujo. En nuestra publicación JEA se utilizó la configuración km1_kahypar_e_mf_jea19.ini .
Para iniciar Kahypar-Ca (utilizando engrosamiento de la comunidad ) optimizando el objetivo (conectividad-1) utilizando el modo Direct K-Way 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
Para iniciar Kahypar en el modo Directo de K-Way (Kahypar-K) optimizando (conectividad-1) ejecución del objetivo:
./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
Para comenzar Kahypar en el modo de bisección recursiva (Kahypar-R) optimizando la ejecución del objetivo de la red de corte:
./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
Todos los parámetros preestablecidos se pueden sobrescribir utilizando las opciones de línea de comandos correspondientes.
Al crear un hipergrafio, Kahypo valida que la entrada es en realidad un hipergrafo correcto, de lo contrario imprimir un error y abortar. Esto se aplica a los archivos de entrada HGR, la interfaz C y la interfaz Python. El costo de tiempo de ejecución de la validación debe ser insignificante en casi todos los casos. Sin embargo, la validación de entrada también se puede deshabilitar utilizando el indicador CMake -DKAHYPAR_INPUT_VALIDATION=OFF .
Además, las advertencias se imprimen para problemas no fatales (por ejemplo, hiperedges con pines duplicados). Para tratar los problemas no fatales como errores duros en su lugar, use la bandera Cmake -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON .
Proporcionamos una interfaz de estilo C simple para usar Kahypar como biblioteca. Tenga en cuenta que esta interfaz aún no es segura. Sin embargo, hay algunas soluciones existentes. La biblioteca se puede construir e instalar a través de
make install.libraryy se puede usar así:
# 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);
} Para compilar el programa usando g++ Run:
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar Nota: Si no se encuentra Boost durante el enlace, es posible que deba agregar -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options al comando.
Para eliminar la biblioteca de su sistema, use el objetivo de desinstalación proporcionado:
make uninstall-kahyparPara compilar la interfaz Python, haga lo siguiente:
mkdir build && cd buildcmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 . Si no tiene Boost instalado, ejecute: cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON lugar. Esto descargará, extraerá y construirá las dependencias necesarias automáticamente.cd pythonmakecp kahypar.so <path-to-site-packages> Site-Packages>Después de eso, puedes usar la Libary Kahypo como esta:
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 )Para obtener más información sobre la funcionalidad de la biblioteca de Python, consulte: Module.cpp
También proporcionamos una versión precompilada como A, que se puede instalar a través de:
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
Gracias a Jordan Jalving (@jalving) Kahypar ahora también ofrece una interfaz Julia, que actualmente se puede encontrar aquí: Kahypar/Kahypar.jl.
La dependencia correspondiente se puede instalar a través de:
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )Después de eso, puede usar Kahypar para dividir sus hipergrafios como este:
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 ha creado una interfaz Java para Kahypar. Consulte el ReadMe para obtener una descripción detallada sobre cómo construir y usar la interfaz.
Le recomendamos que informe cualquier problema con Kahypo a través del sistema de seguimiento de problemas GitHub del proyecto.
Kahypar es el software gratuito proporcionado bajo la Licencia Pública General de GNU (GPLV3). Para obtener más información, consulte el archivo de copia. Distribuimos este marco libremente para fomentar el uso y el desarrollo de herramientas de división de hipergrafías. Si usa Kahypar en un entorno académico, cite los documentos apropiados. Si está interesado en una licencia comercial, contácteme.
// 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 está interesado en contribuir al marco de Kahypar, no dude en contactarme o crear un problema en el sistema de seguimiento de problemas.
