Programa para la computación Descomposición en árbol de un gráfico

22

¿Alguien sabe de un programa de código abierto para calcular la descomposición de gráficos en árbol para una "k" fija (ancho)? Sé que el problema de encontrar Tree-Decomposition es NP-Hard para la variable "k", pero mis instancias de entrada serán realmente pequeñas (~ 10 nodos) y "k" es fijo.

ds.algorithms graph-theory graph-algorithms software treewidth Kaveh
fuente
1
Meta discusión: meta.cstheory.stackexchange.com/questions/1101/… . Visite el sitio meta antes de publicar cualquier respuesta. Me pregunto si esta pregunta está dentro del alcance o no.
Suresh Venkat

Respuestas:

22

Algunos de estos programas pueden ayudarte. (Sin embargo, no todos son de código abierto).

* 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
fuente
No veo la relevancia de dlib; El algoritmo Bayesian Network Join Tree está relacionado con el ancho del árbol, pero esta implementación no parece ayudar a calcular la descomposición del árbol. TreeDecomp de Radu Marinescu también podría ser útil: graphmod.ics.uci.edu/group/treeDecomp
András Salamon
3
La función crear árbol de unión en dlib toma un gráfico y devuelve su descomposición en árbol.
Davis King el
@Davis: Gracias por el puntero explícito, lo perdí en la documentación.
András Salamon
1
El enlace a LibTW redirige a la firma consultora (holandesa) del autor. ¿Hay una nueva URL?
Jeffε
7

n∼10kn≤13k≤4

Tiene aproximadamente 170 líneas de código y es GPL (o MIT o BSD o lo que sea que necesite).

Pål GD
fuente
5

n≤150

Fasermaler
fuente
1

También puede estar interesado en los algoritmos más modernos FlowCutter ( GitHub ) y los algoritmos de Tamaki et al. ( GitHub )

delete000
fuente