Gostaria de calcular a largura da árvore de um gráfico. Existem realmente boas heurísticas para outros problemas de gráficos NP-hard, como VF2 para isomorfismo de subgráficos, com código disponível no igraph, por exemplo. Eu tentei eles nos meus gráficos e acho que eles correm muito rápido para os meus dados.
Existem algoritmos rápidos para o cálculo da largura de árvore em uma veia semelhante?
Respostas:
Até onde eu sei, o estado da arte é o que é relatado em
Hans L. Bodlaender, Fedor V. Fomin, Arie MCA Koster, Dieter Kratsch e Dimitrios M. Thilikos (2012), "Em algoritmos exatos para a largura de árvore", ACM Transactions on Algorithms 9 (1): A12, doi: 10.1145 / 2390176.2390188 .
Os métodos descritos não incluem uma implementado algoritmo com algumas otimizações heurísticos para torná-lo mais rápido na prática.O∗(2n)
fonte
Escrevi um artigo chamado A Fast Parallel Branch and Bound Algorithm for Treewidth, no ICTAI 2011. Ele pode calcular a largura de árvore em vários núcleos . Usei muitas heurísticas e passei muito tempo refinando o programa.
Eu era um estudante aleatório de graduação na China e não consegui uma boa conferência. Mas com base nos resultados dos meus experimentos, acho que meu programa é muito rápido. Resolvi muitos benchmarks não resolvidos na lib Treewidth, e meu programa foi 40 vezes mais rápido que um algoritmo proposto por Zhou e Hansen no IJCAI 09.
Não estou mais trabalhando neste tópico. Mas se meu trabalho anterior for útil, você pode baixar meu programa (src e exe) em http://www.callowbird.com/undergrad-stuff.html e tentar. (ainda assim, é muito, muito lento em uma instância um pouco maior)
fonte
fonte
Aqui estão duas pesquisas sobre algoritmos para calcular a largura da árvore que podem ser úteis. O primeiro possui comparações empíricas e algoritmos diversos implementados como uma biblioteca Java.
fonte
O Sage não sabe calcular exatamente a largura da árvore, mas pode fornecer a largura de caminho de pequenos gráficos.
http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html
Eu ficaria muito feliz em saber que existe algo implementado e público para calcular a decomposição de árvores, embora
:-)
Nathann
fonte