Programm zur Berechnung der Baumzerlegung eines Graphen

22

Kennt jemand ein Open-Source-Programm zur Berechnung der Baumzerlegung von Graphen für ein festes "k" (Breite)? Ich weiß, dass das Problem beim Auffinden der Baumzerlegung für die Variable "k" NP-schwer ist, aber meine Eingabeinstanzen sind sehr klein (~ 10 Knoten) und "k" ist behoben.

ds.algorithms graph-theory graph-algorithms software treewidth Kaveh
quelle
1
Metadiskussion : meta.cstheory.stackexchange.com/questions/1101/… . Bitte besuchen Sie die Meta-Site, bevor Sie Antworten veröffentlichen. Ich frage, ob diese Frage in den Geltungsbereich fällt oder nicht.
Suresh Venkat

Antworten:

22

Einige dieser Programme könnten Ihnen helfen. (Nicht alle von ihnen sind 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
quelle
Ich sehe die Relevanz von dlib nicht; Der Bayesian Network Join Tree-Algorithmus ist mit der Baumbreite verwandt, aber diese Implementierung scheint bei der Berechnung einer Baumzerlegung nicht hilfreich zu sein. Radu Marinescus treeDecomp könnte auch nützlich sein: graphmod.ics.uci.edu/group/treeDecomp
András Salamon
3
Die Funktion create join tree in dlib erstellt ein Diagramm und gibt dessen Baumzerlegung zurück.
Davis King
@Davis: Danke für den expliziten Zeiger, den ich in der Dokumentation verpasst habe.
András Salamon
1
Der Link zu LibTW leitet zur niederländischen Beratungsfirma des Autors weiter. Gibt es eine neue URL?
Jeffs
7

n∼10kn≤13k≤4

Es sind ungefähr 170 Codezeilen und es ist GPL (oder MIT oder BSD oder was auch immer Sie brauchen sollten).

Pål GD
quelle
5

n≤150

Fasermaler
quelle
1

Vielleicht interessieren Sie sich auch für die moderneren Algorithmen FlowCutter ( GitHub ) und die Algorithmen von Tamaki et al. ( GitHub )

delete000
quelle