kahypar
v.1.3.5
Os hipergrafos são uma generalização de gráficos, onde cada borda (hiper) (também chamada de rede) pode conectar mais de dois vértices. O problema de particionamento de hipergrafos K é a generalização do conhecido problema de particionamento de gráficos: Partição O vértice definido em blocos disjuntos K de tamanho limitado (no máximo 1 + ε vezes o tamanho médio do bloco), minimizando uma função objetiva definida nas redes.
As duas funções objetivas mais proeminentes são as métricas de rede cortada e conectividade (ou λ-1). A rede de corte é uma generalização direta do objetivo do corte da borda no particionamento de gráficos (ou seja, minimizando a soma dos pesos dessas redes que conectam mais de um bloco). A métrica de conectividade também leva em consideração o número real λ de blocos conectados por uma rede. Ao somando os valores (λ-1) de todas as redes, um modela com precisão o volume total de comunicação de multiplicação de vetor de matriz esparsa paralela e mais uma vez recebe uma métrica que reverte para os gráficos simples para os gráficos simples.
Kahypar é uma estrutura de particionamento de hipergrafos multinível para otimizar o corte e o (λ- 1) -métrico. Ele suporta a bissecção recursiva e a partição direta de K-Way . Como um algoritmo multinível, consiste em três fases: na fase grossa , a hipergrafia é grosseira para obter uma hierarquia de hipergrafos menores. Depois de aplicar um algoritmo de particionamento inicial ao menor hipergrafado na segunda fase, o grosso é desfeito e, em cada nível, um método de pesquisa local é usado para melhorar a partição induzida pelo nível mais grosso. Kahypar instancia a abordagem multinível em sua versão mais extrema, removendo apenas um único vértice em todos os níveis da hierarquia. Ao usar essa abordagem de nível n muito fino, combinado com fortes heurísticas de pesquisa local, ele calcula soluções de alta qualidade. Seus algoritmos e resultados experimentais detalhados são apresentados em várias publicações de pesquisa.
Particionamento de hipergraph com pesos variáveis de blocos
Kahypar tem suporte para pesos variáveis de blocos. Se a opção de linha de comando --use-individual-part-weights=true for usada, o Partiote tenta particionar o hipergraph, de modo que cada Block VX tenha um peso na maioria dos BX, onde BX pode ser especificado para cada bloco individualmente usando o parâmetro da linha de comando --part-weights= B1 B2 B3 ... Bk-1 . Como a estrutura ainda não suporta particionamento perfeitamente equilibrado, os limites superiores precisam ser um pouco maiores que o peso total de todos os vértices do hipergraph. Observe que esse recurso ainda é experimental.
Particionamento de hipergraph com vértices fixos
O particionamento de hipergrafias com vértices fixos é uma variação do particionamento padrão de hipergraph. Nesse problema, há uma restrição adicional na atribuição de bloqueios de alguns vértices, ou seja, alguns vértices são pré -projetados para blocos específicos antes da partição com a condição de que, depois de particionar os vértices "livres" restantes, os vértices fixos ainda estão no bloco que foram atribuídos. O parâmetro da linha de comando --fixed / -f pode ser usado para especificar um arquivo de fixação no formato de arquivo Hmetis Fix. Para uma hipergraf com v vértices, o arquivo fix consiste em l linhas - uma para cada vértice. A linha i th contém -1 para indicar que o vértice está livre para mover ou <part id> para indicar que esse vértice deve ser pré -projetado para bloquear <part id> . Observe que os IDs da peça começam em 0.
Atualmente, Kahypar suporta três políticas de contração diferentes para particionar com vértices fixos:
free_vertex_only permite todas as contrações nas quais o parceiro de contração é um vértice livre , ou seja, permite contrações de pares de vértices onde ambos os vértices são livres ou um vértice é fixo e o outro vértice é gratuito.fixed_vertex_allowed Permite adicionalmente contrações de dois vértices fixos, desde que ambos sejam pré -projetados para o mesmo bloco. Com base em experimentos preliminares, atualmente esta é a política padrão.equivalent_vertices permite apenas contrações de pares de vértices que consistem em dois vértices livres ou dois vértices fixos pré -projetados para o mesmo bloco.Estrutura evolutiva (Kahypar-e)
Kahypar-e aprimora Kahypar com uma estrutura evolutiva, conforme descrito em nossa publicação GECCO'18. Dada uma quantidade bastante grande de tempo de execução, esse algoritmo multinível memético tem um desempenho melhor do que as execuções repetidas de configurações não -voltárias de Kahypar, Hmetis e Patoh. O parâmetro da linha de comando --time-limit=xxx pode ser usado para definir o tempo de execução máximo (em segundos). Parâmetro --partition-evolutionary=true permite particionamento evolutivo.
Melhorando as partições existentes
O Kahypar usa as ciclas V V-WAY direta para tentar melhorar uma partição existente especificada via parâmetro --part-file=</path/to/file> . O número máximo de ciclos V pode ser controlado via parâmetro --vcycles= .
Particionamento direcionado hipergrafos aciclicos
Embora o código ainda não tenha sido mesclado no repositório principal, existe um garfo que suporta particionamento de hipergrafias aciclicas. Mais detalhes podem ser encontrados na publicação da conferência correspondente.
Utilizamos os perfis de desempenho para comparar o Kahypar com outros algoritmos de particionamento em termos de qualidade da solução. Para um conjunto de
algoritmos e um conjunto de referência
contendo
Instâncias, a taxa de desempenho
relata o corte calculado pelo Partiote P, por exemplo, I ao menor corte mínimo de todos os algoritmos, ou seja,
.
O perfil de desempenho
do algoritmo P é então dado pela função
.
Para otimização de conectividade, as taxas de desempenho são calculadas usando os valores de conectividade
em vez dos valores de corte. O valor de
corresponde à fração de instâncias para as quais o Partiote P calcou a melhor solução, enquanto é a probabilidade de que uma taxa de desempenho está dentro de um fator de
da melhor proporção possível. Observe que como os perfis de desempenho permitem avaliar apenas o desempenho de cada algoritmo em relação ao melhor algoritmo, o
Os valores não podem ser usados para classificar os algoritmos (ou seja, para determinar qual algoritmo é o segundo melhor etc.).
Em nossa análise experimental, os gráficos do perfil de desempenho são baseados nas melhores soluções (ou seja, conectividade/corte mínimo ) cada algoritmo encontrado para cada instância. Além disso, escolhemos parâmetros
Para todos P , eu e
de modo que uma taxa de desempenho
Se e somente se o algoritmo P calculou uma solução inviável, por exemplo, e
se e somente se o algoritmo não puder calcular uma solução, por exemplo, I dentro do prazo fornecido. Em nossos gráficos de perfil de desempenho, as taxas de desempenho correspondentes a soluções inviáveis serão mostradas no x -tick no eixo x , enquanto instâncias que não puderam ser particionadas dentro do prazo são mostradas implicitamente por uma linha que sai do gráfico abaixo
. Como as taxas de desempenho são fortemente paradas à direita, os gráficos do perfil de desempenho são divididos em três segmentos com diferentes faixas para o parâmetro para refletir várias áreas de interesse. O primeiro segmento destaca pequenos valores (
), enquanto o segundo segmento contém resultados para todas as instâncias que estão de acordo com um fator de
pior que a melhor proporção possível. O último segmento contém todas as proporções restantes, ou seja, instâncias para as quais alguns algoritmos tiveram um desempenho consideravelmente pior do que o melhor algoritmo, instâncias para as quais os algoritmos produziram soluções inviáveis e instâncias que não puderam ser particionadas dentro do tempo de tempo.
Nas figuras, comparamos o kahypar com o patoh em qualidade (patoh-q) e o modo padrão (patoh-d), o k-way (hmetis-k) e a variante de bissecção recursiva (hmetis-r.3.1 e hymetis 2.0 (p1), o zoltano usando a distância de aloção alondan-alondrian (zoltn-algengan-alondraic a distância de alondana (zoltan) (p1), o zoltano de alonda-noltn-alondrian-alondraic (zoltan), o zoltan, o zoltan, o zoltan, o zoltan e a distância de alondan-alondrian (zoltn), o zoltan, o zoltan, o zoltan e o raciocínio do zoltan. Algoritmo.
Qualidade da solução 
Tempo de execução 
Fornecemos recursos adicionais para todas as publicações relacionadas a Kahypar:
| kkahypar-sea20 / RKAHYPAR-SEA20 | Sea'20 | Papel | Tr | Deslizamentos | Resultados experimentais |
|---|---|---|---|---|---|
| kkahypar / rkahypar | - | Dissertação | - | Deslizamentos | Resultados experimentais |
| Kahypar-mf / KAHYPAR-R-MF | Sea'18 / Jea'19 | Papel do mar / Papel Jea | Tr | Deslizamentos | Resultados experimentais: Sea / Jea |
| Kahypar-e (evohgp) | GECCO'18 | Papel | Tr | Deslizamentos | Resultados experimentais |
| KAHYPAR-CA | Sea'17 | Papel | - | Deslizamentos | Resultados experimentais |
| Kahypar-k | Alenex'17 | Papel | - | Deslizamentos | Resultados experimentais |
| Kahypar-r | Alenex'16 | Papel | Tr | Deslizamentos | Resultados experimentais |
A estrutura de particionamento de hipergrafos de Karlsruhe requer:
g++ versão 9 ou superior ou clang versão 11.0.3 ou superior.-DKAHYPAR_USE_MINIMAL_BOOST=ON sinalizador ao comando cmake para baixar, extrair e criar as dependências necessárias automaticamente. Clone o repositório, incluindo submódulos:
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
Crie um diretório de construção: mkdir build && cd build
Execute cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
Run Make: make
Os testes são executados automaticamente enquanto o projeto é construído. Além disso, um alvo test é fornecido. Os testes de integração de ponta a ponta podem ser iniciados com: make integration_tests . O perfil pode ser ativado via sinalizador cmake: -DENABLE_PROFILE=ON .
O programa independente pode ser construído via make KaHyPar . O binário estará localizado em: build/kahypar/application/ .
Kahypar possui vários parâmetros de configuração. Para uma lista de todos os parâmetros possíveis, execute: ./KaHyPar --help . Utilizamos o formato Hmetis para o arquivo hipergraph de entrada, bem como o arquivo de saída de partição.
O parâmetro da linha de comando --quiet=1 pode ser usado para suprimir toda a saída de log. Se você estiver usando as interfaces da biblioteca, adicionar quiet=1 ao arquivo de configuração .ini correspondente tem o mesmo efeito.
Fornecemos duas configurações de estrutura padrão - uma para bipartição recursiva ( R Kahypar) e outra para particionamento direto de K -Way ( K Kahypar).
Em geral, recomendamos o uso de K Kahypar, pois ele tem um desempenho melhor que o R Kahypar em termos de tempo de execução e qualidade da solução.
Para iniciar o K Kahypar otimizando a execução objetiva (conectividade 1) :
./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 o K Kahypartizando a execução do objetivo da rede 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 o R Kahypar otimizando a execução objetiva (conectividade 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 o R Kahypar otimizando a execução do Objetivo Net Cut :
./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 o algoritmo memético k kahypar -e otimizando a execução objetiva (conectividade - 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
Além disso, fornecemos predefinições diferentes que correspondem às configurações usadas nas publicações em Alenex'16, Alenex'17, Sea'17, Sea'18, Gecco'18, bem como em nosso artigo da JEA Journal e na dissertação de Sebastian Schlag. Essas configurações estão localizadas na pasta Config/Old_Reference_Configs. Para usar essas configurações, você deve verificar a Release 1.1.0 do Kahypar, uma vez que algum código antigo foi removido na versão mais atual.
Para iniciar o Kahypar-MF (usando o refinamento baseado em fluxo ) otimizando o objetivo (conectividade-1) usando o modo K-Way direto 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 o Kahypar-MF (usando o refinamento baseado em fluxo ) otimizando o objetivo da rede de corte usando o modo K-Way direto execute:
./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 o evohgp/kahypar-e otimizando o objetivo (conectividade-1) usando o modo K-Way direto
./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
Observe que a configuração km1_direct_kway_gecco18.ini é baseada em Kahypar-CA. No entanto, Kahypar-E também trabalha com melhorias locais baseadas em fluxo. Em nossa publicação JEA, foi utilizada a configuração km1_kahypar_e_mf_jea19.ini .
Para iniciar o Kahypar-CA (usando o grosamento com reconhecimento da comunidade ) otimizando o objetivo (conectividade-1) usando o modo K-Way direto 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 o Kahypar no modo K-Way direto (Kahypar-k), otimizando a execução objetiva (conectividade-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
Para iniciar Kahypar no modo de bissecção recursiva (Kahypar-R), otimizando a execução objetiva da rede cortada:
./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 os parâmetros predefinidos podem ser substituídos usando as opções de linha de comando correspondentes.
Ao criar um hipergraph, Kahypar valida que a entrada é na verdade um hipergraph correto, imprimindo um erro e abortando. Isso se aplica aos arquivos de entrada HGR, a interface C e a interface Python. O custo de tempo de execução da validação deve ser insignificante em quase todos os casos. No entanto, a validação de entrada também pode ser desativada usando o sinalizador cmake -DKAHYPAR_INPUT_VALIDATION=OFF .
Além disso, os avisos são impressos para questões não fatais (por exemplo, hiperedges com pinos duplicados). Para tratar problemas não fatais como erros difíceis, use o sinalizador cmake -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON .
Fornecemos uma interface simples no estilo C para usar o Kahypar como uma biblioteca. Observe que essa interface ainda não está segura para threads. No entanto, existem algumas soluções alternativas. A biblioteca pode ser construída e instalada via
make install.librarye pode ser usado assim:
# 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 o programa usando g++ Run:
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar NOTA: Se o Boost não for encontrado durante a ligação, pode ser necessário adicionar -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options no comando.
Para remover a biblioteca do seu sistema, use o destino desinstalado fornecido:
make uninstall-kahyparPara compilar a interface Python, faça o seguinte:
mkdir build && cd buildcmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 . Se você não tiver o Boost instalado, execute: cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON em vez disso. Isso baixará, extrairá e criará as dependências necessárias automaticamente.cd pythonmakecp kahypar.so <path-to-site-packages>Depois disso, você pode usar o Kahypar Libary assim:
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 obter mais informações sobre a funcionalidade da biblioteca Python, consulte: Module.cpp
Também fornecemos uma versão pré -compilada como A, que pode ser instalada via:
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
Graças a Jordan Jalving (@Jalving) Kahypar agora também oferece uma interface Julia, que atualmente pode ser encontrada aqui: Kahypar/KahyPar.jl.
A dependência correspondente pode ser instalada via:
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )Depois disso, você pode usar o Kahypar para particionar seus hipergrafos 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 criou uma interface Java para Kahypar. Consulte o ReadMe para obter uma descrição detalhada sobre como criar e usar a interface.
Incentivamos você a relatar quaisquer problemas com Kahypar por meio do sistema de rastreamento de problemas do GitHub do projeto.
Kahypar é um software livre fornecido sob a licença pública geral da GNU (GPLV3). Para mais informações, consulte o arquivo de cópia. Distribuímos essa estrutura livremente para promover o uso e o desenvolvimento de ferramentas de particionamento de hipergrafes. Se você usar o Kahypar em um ambiente acadêmico, cite os papéis apropriados. Se você estiver interessado em uma licença comercial, entre em contato comigo.
// 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}
}
Se você estiver interessado em contribuir para a estrutura Kahypar, não hesite em entrar em contato comigo ou criar um problema no sistema de rastreamento de problemas.
