Algorytmy szybkiej prędkości

18

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?

Felix
źródło
1
fyi ostatnio treewidth został połączony z twardością SAT przez Gaspersa / Szeidera w FOCS, mam nadzieję usłyszeć od innych na tym czacie / dyskusji
dniu

Odpowiedzi:

19

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(2)n)

David Eppstein
źródło
2
Dziękuję Ci. Odniesienia 2, 8 i 15, które podają heurystykę górną i dolną, mogą być w praktyce najbardziej przydatne z tego artykułu.
felix
10

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)

Yang Yuan
źródło
5

O(2)k)

M. kanté
źródło
1
2)O(k)O(dokn)do
5

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.

Istnieje wiele algorytmów do obliczania górnej granicy, dolnej granicy lub dokładnej szerokości wykresu. Wdrożyliśmy wiele heurystyki górnej i dolnej granicy oraz dwa dokładne algorytmy (programowanie dynamiczne oraz algorytm rozgałęzienia i ograniczenia). Ten raport porównuje różne rodzaje algorytmów i pokazuje, że niektóre algorytmy są preferowane.

Treewidth jest parametrem grafu o kilku interesujących zastosowaniach teoretycznych i praktycznych. W tej ankiecie dokonano przeglądu wyników algorytmicznych dotyczących określenia szerokości danego wykresu i znalezienia rozkładu drzewa o małej szerokości. Omówiono oba wyniki teoretyczne, ustanawiające asymptotyczną złożoność obliczeniową problemu, jako prace eksperymentalne nad heurystyką (zarówno dla górnych granic, jak i dolnych granic), przetwarzanie wstępne, dokładne algorytmy i przetwarzanie końcowe.

vzn
źródło