Program untuk menghitung dekomposisi Tree pada grafik

22

Apakah ada yang tahu tentang program open-source untuk menghitung dekomposisi Tree dari grafik untuk "k" (lebar) yang diperbaiki? Saya tahu bahwa masalah menemukan Tree-Decomposition adalah NP-Hard untuk variabel "k", tetapi instance input saya akan sangat kecil (~ 10 node) dan "k" sudah diperbaiki.

ds.algorithms graph-theory graph-algorithms software treewidth Kaveh
sumber
1
Diskusi meta: meta.cstheory.stackexchange.com/questions/1101/… . Silakan kunjungi situs meta sebelum memposting jawaban apa pun - Saya mempertanyakan apakah pertanyaan ini dalam cakupan atau tidak.
Suresh Venkat

Jawaban:

22

Beberapa perangkat lunak ini mungkin membantu Anda. (Namun tidak semuanya 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
sumber
Saya tidak melihat relevansi dlib; algoritma bayesian network join tree terkait dengan treewidth tetapi implementasi ini sepertinya tidak membantu dengan komputasi dekomposisi pohon. TreeDecomp Radu Marinescu mungkin juga berguna: graphmod.ics.uci.edu/group/treeDecomp
András Salamon
3
Fungsi create join tree di dlib mengambil grafik dan mengembalikan dekomposisi pohonnya.
Davis King
@ David: Terima kasih untuk pointer eksplisit, melewatkan itu di dokumentasi.
András Salamon
1
Tautan ke LibTW dialihkan ke perusahaan konsultan penulis (Belanda). Apakah ada URL baru?
Jeffε
7

n∼10kn≤13k≤4

Ini sekitar 170 baris kode dan itu adalah GPL (atau MIT atau BSD atau apa pun yang Anda butuhkan).

Pål GD
sumber
5

n≤150

Fasermaler
sumber
1

Anda mungkin juga tertarik dengan algoritma FlowCutter ( GitHub ) yang lebih modern dan algoritme oleh Tamaki et al. ( GitHub )

delete000
sumber