Chciałbym obliczyć szerokość wykresu. Istnieją naprawdę dobre heurystyki dla innych problemów związanych z grafem NP-twardym, takich jak VF2 dla izomorfizmu podgraficznego , z kodem dostępnym na przykład w igraph . Wypróbowałem je na moich wykresach i okazało się, że działają bardzo szybko dla moich danych.
Czy są jakieś szybkie algorytmy do obliczania szerokości w podobnym stylu?
Odpowiedzi:
O ile mi wiadomo, stan techniki jest opisany w
Hans L. Bodlaender, Fedor V. Fomin, Arie MCA Koster, Dieter Kratsch i Dimitrios M. Thilikos (2012), „O dokładnych algorytmach dla szerokości”, ACM Transactions on Algorytmy 9 (1): A12, doi: 10.1145 / 2390176.2390188 .
Opisane tam metody obejmują zaimplementowany algorytm z pewnymi optymalizacjami heurystycznymi, aby uczynić go szybszym w praktyce.O∗( 2n)
źródło
Napisałem artykuł zatytułowany A Fast Parallel Branch and Bound Algorytm for Treewidth, w ICTAI 2011. Potrafi obliczyć szerokość w wielu rdzeniach . Wykorzystałem wiele heurystyki i spędziłem dużo czasu na doskonaleniu programu.
Byłem przypadkowym studentem studiów licencjackich w Chinach i nie dotarłem na dobrą konferencję. Ale na podstawie wyników mojego eksperymentu sądzę, że mój program jest bardzo szybki. Rozwiązałem wiele nierozwiązanych testów wydajności w bibliotece Treewidth, a mój program był 40 razy szybszy niż algorytm zaproponowany przez Zhou i Hansena w IJCAI 09 ..
Nie pracuję już nad tym tematem. Ale jeśli moja poprzednia praca jest pomocna, możesz pobrać mój program (src i exe) ze strony http://www.callowbird.com/undergraduate-stuff.html i spróbować. (wciąż jest bardzo bardzo wolny w nieco większej instancji)
źródło
źródło
Oto dwie ankiety dotyczące algorytmów obliczania szerokości poprzecznej, które mogą być pomocne. Pierwszy zawiera porównania empiryczne i różne algorytmy zaimplementowane jako biblioteka Java.
źródło
Sage nie wie dokładnie, jak dokładnie obliczyć szerokość, ale może zapewnić przepustowość małych wykresów.
http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html
Byłbym bardzo zadowolony, gdybym dowiedział się, że istnieje coś zaimplementowanego i publicznego do obliczania rozkładów drzew, chociaż
:-)
Nathann
źródło