Programa para calcular a decomposição em árvore de um gráfico

22

Alguém conhece um programa de código aberto para calcular a decomposição em árvore de gráficos para um "k" (largura) fixo? Eu sei que o problema de encontrar a Decomposição em Árvore é NP-Difícil para a variável "k", mas minhas instâncias de entrada serão realmente pequenas (~ 10 nós) e "k" é corrigido.

ds.algorithms graph-theory graph-algorithms software treewidth Kaveh
fonte
11
Meta discussão: meta.cstheory.stackexchange.com/questions/1101/… . Visite o meta site antes de postar qualquer resposta - estou questionando se esta questão está no escopo ou não.
Suresh Venkat

Respostas:

22

Alguns desses softwares podem ajudá-lo. (Porém, nem todos eles são de código aberto.)

* TreeD http://www.itu.dk/people/sathi/treed/

* dlib http://dlib.net/

* QuickBB http://www.cs.washington.edu/homes/vgogate/quickbb.html

* Hypertree http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html

* LibTW http://www.treewidth.com/treewidth/

Snowie
fonte
Não vejo a relevância do dlib; o algoritmo de árvore de junção da rede bayesiana está relacionado à largura da árvore, mas essa implementação não parece ajudar no cálculo de uma decomposição de árvore. TreeDecomp de Radu Marinescu também pode ser útil: graphmod.ics.uci.edu/group/treeDecomp
András Salamon
3
A função create join tree no dlib pega um gráfico e retorna sua decomposição em árvore.
Davis rei
@ David: Obrigado pelo ponteiro explícito, perdeu isso na documentação.
András Salamon
11
O link para LibTW redireciona para a empresa de consultoria do autor (holandês). Existe um novo URL?
Jeffε
7

n∼10kn≤13k≤4

São aproximadamente 170 linhas de código e são GPL (ou MIT ou BSD ou o que você precisar).

Pål GD
fonte
5

n≤150

Fasermaler
fonte
1

Você também pode estar interessado nos algoritmos mais modernos FlowCutter ( GitHub ) e nos algoritmos de Tamaki et al. ( GitHub )

delete000
fonte