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

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)}

$2^{O(k)}$

O (c^{k} n)

$O(c^k n)$

c

$c$

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.

treewidth.com / Computing treewidth with Libtw Dijk, Heuvel, Slob

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.

Discovering Treewidth (2005) Hansa L. Bodlaendera

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

3

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

— Nathann Cohen
źródło

1

k

$k$