Programme de calcul de la décomposition en arbre d'un graphe

22

Quelqu'un connaît-il un programme open-source pour calculer la décomposition arborescente des graphiques pour un "k" fixe (largeur)? Je sais que le problème de trouver Tree-Decomposition est NP-Hard pour la variable "k", mais mes instances d'entrée seront vraiment petites (~ 10 nœuds) et "k" est fixe.

ds.algorithms graph-theory graph-algorithms software treewidth Kaveh
la source
1
Méta discussion: meta.cstheory.stackexchange.com/questions/1101/… . Veuillez visiter le méta-site avant de poster des réponses - je me demande si cette question est dans le champ d'application ou non.
Suresh Venkat

Réponses:

22

Certains de ces logiciels peuvent vous aider. (Cependant, tous ne sont pas open-source.)

* 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
la source
Je ne vois pas la pertinence de dlib; l'algorithme de jointure du réseau bayésien est lié à la largeur d'arbre, mais cette implémentation ne semble pas aider à calculer une décomposition d'arbre. TreeDecomp de Radu Marinescu pourrait également être utile: graphmod.ics.uci.edu/group/treeDecomp
András Salamon
3
La fonction create join tree dans dlib prend un graphe et retourne sa décomposition d'arbre.
Davis King
@Davis: Merci pour le pointeur explicite, manqué cela dans la documentation.
András Salamon
1
Le lien vers LibTW redirige vers le cabinet de conseil de l'auteur (néerlandais). Y a-t-il une nouvelle URL?
Jeffε
7

n∼10kn≤13k≤4

C'est environ 170 lignes de code et c'est GPL (ou MIT ou BSD ou tout ce dont vous avez besoin).

Pål GD
la source
5

n≤150

Fasermaler
la source
1

Vous pouvez également être intéressé par les algorithmes plus modernes FlowCutter ( GitHub ) et les algorithmes de Tamaki et al. ( GitHub )

delete000
la source