Saya ingin menghitung treewidth grafik. Ada heuristik yang benar-benar bagus untuk masalah grafik NP-hard lainnya seperti VF2 untuk subgraph isomorphism, dengan kode yang tersedia dalam igraph misalnya. Saya telah mencobanya pada grafik saya dan saya menemukan mereka berjalan sangat cepat untuk data saya.
Apakah ada algoritma cepat untuk perhitungan treewidth dalam nada yang sama?
Jawaban:
Sejauh yang saya tahu, keadaan seni adalah apa yang dilaporkan
Hans L. Bodlaender, Fedor V. Fomin, Arie MCA Koster, Dieter Kratsch, dan Dimitrios M. Thilikos (2012), "Pada algoritma yang tepat untuk treewidth", ACM Transaksi pada Algoritma 9 (1): A12, doi: 10.1145 / 2390176.2390188 .
Metode yang dijelaskan di sini termasuk algoritma yang diimplementasikan dengan beberapa optimasi heuristik untuk membuatnya lebih cepat dalam praktik.HAI∗( 2n)
sumber
Saya menulis sebuah makalah bernama A Fast Parallel Branch dan Algoritma Bound untuk Treewidth, di ICTAI 2011. Ia dapat menghitung treewidth dalam multi-core . Saya menggunakan banyak heuristik dan menghabiskan banyak waktu menyempurnakan program.
Saya adalah seorang mahasiswa sarjana acak di China dan tidak berhasil menghadiri konferensi yang baik. Tetapi berdasarkan hasil percobaan saya, saya pikir program saya sangat cepat. Saya memecahkan banyak tolok ukur yang belum terpecahkan di Treewidth lib, dan program saya 40 kali lebih cepat daripada algoritma yang diusulkan oleh Zhou dan Hansen di IJCAI 09 ..
Saya tidak mengerjakan topik ini lagi. Tetapi jika pekerjaan saya sebelumnya sangat membantu, Anda dapat mengunduh program saya (src dan exe) dari http://www.callowbird.com/undergrad-stuff.html , dan cobalah. (masih, ini sangat sangat lambat pada contoh yang sedikit lebih besar)
sumber
sumber
Berikut adalah dua survei tentang algoritma untuk menghitung treewidth yang mungkin bermanfaat. Yang pertama memiliki perbandingan empiris, dan memiliki berbagai algoritma diimplementasikan sebagai perpustakaan Java.
sumber
Sage tidak tahu bagaimana cara menghitung treewidth dengan tepat tetapi dapat memberi Anda lebar jalur grafik kecil.
http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html
Saya akan sangat senang mengetahui bahwa ada sesuatu yang diterapkan dan publik untuk menghitung dekomposisi pohon, meskipun
:-)
Nathann
sumber