Algoritmos rápidos de largura de árvore

18

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?

felix
fonte
1
fyi recentemente treewidth tem sido ligado a dureza SAT por Gaspers / Szeider em FOCS, a esperança de ouvir de outros em que conversa / discussão
vzn

Respostas:

19

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)

David Eppstein
fonte
2
Obrigado. As referências 2, 8 e 15 que fornecem heurísticas dos limites superior e inferior podem, na prática, ser as mais úteis desse artigo.
Felix
10

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)

Yang Yuan
fonte
5

O(2k)

M. kanté
fonte
1
2O(k)O(ckn)c
5

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.

Existem muitos algoritmos para calcular um limite superior, um limite inferior ou a largura de árvore exata de um gráfico. Implementamos muitas heurísticas de limite superior e inferior e dois algoritmos exatos (uma programação dinâmica e um algoritmo de ramificação e limite). Este relatório compara os diferentes tipos de algoritmos e mostra que alguns algoritmos são preferidos.

A largura da árvore é um parâmetro gráfico com várias aplicações teóricas e práticas interessantes. Esta pesquisa analisa os resultados algorítmicos para determinar a largura da árvore de um determinado gráfico e encontrar uma decomposição de árvore de pequena largura. São discutidos os dois resultados teóricos, estabelecendo a complexidade computacional assintótica do problema, como trabalho experimental em heurísticas (tanto para limites superiores quanto inferiores), pré-processamento, algoritmos exatos e pós-processamento.

vzn
fonte