Czy drzewa cięte łączem są kiedykolwiek wykorzystywane w praktyce do obliczeń maksymalnego przepływu lub innych zastosowań?

20

Wiele algorytmów maksymalnego przepływu, które zwykle widzę zaimplementowanych, algorytm Dinica, push push i inne, mogą mieć asymptotyczny koszt czasu ulepszony dzięki zastosowaniu dynamicznych drzew (znanych również jako drzewa cięte łączem).

  • Wciśnij etykietę w trybie lub O ( V 3 ) lub O ( V 2 √)O(V.2)mi)O(V.3))normalnie, ale z dynamicznymi drzewamiO(VElog(V2/E))O(V.2)mi)O(V.milog⁡(V.2)/mi))
  • Algorytm Dinica działa w , ale z dynamicznymi drzewami O ( V E log ( V ) )O(V.2)mi)O(V.milog⁡(V.))

Jednak praktyczne implementacje algorytmów maksymalnego przepływu w większości bibliotek wydają się nie wykorzystywać tej struktury danych. Czy drzewa dynamiczne były kiedykolwiek wykorzystywane w praktyce do obliczania maksymalnego przepływu? Czy też niosą ze sobą zbyt duży koszt, aby były przydatne w rzeczywistych rozmiarach problemów?

Czy istnieją inne domeny problematyczne, w których wykorzystywane są drzewa cięte łączem?

To pytanie jest związane z pytaniem, które zadałem na cstheory: Czy któryś z najnowszych algorytmów maksymalnego przepływu jest praktyczny?

reference-request graphs data-structures network-flow Rob Lachlan
źródło
przegląd / opis drzewa wyciętych linków, ale tylko stany „jest użyteczny w aplikacjach takich jak Network Flow”
vzn
z ankiety tarjan cytowanej przez Reza, zasadniczo liniowe algorytmy czasowe działają bardzo dobrze / najlepiej dla umiarkowanej liczby wierzchołków / krawędzi, a następnie istnieje próg progowy większych wierzchołków / krawędzi, w których algorytmy logarytmiczne przewyższają algorytm liniowy. więc logarytmiczne fns dostępu są przydatne i mogą być znacznie lepsze w przypadku bardzo dużych wykresów.
vzn

Odpowiedzi:

7

Istnieje artykuł zatytułowany „ Drzewa dynamiczne w praktyce ”, w którym dokonano przeglądu praktycznego wdrożenia.

Inne kategorie, w których drzewo Link-Cut można efektywnie wykorzystać, to Indeksowanie baz danych . Można to znaleźć w książce „ Techniki indeksu baz danych ”.

Reza
źródło
myślę, że to wymaga nieco rozwinięcia. drzewa są oczywiście przydatne do indeksów, ale w jakich warunkach drzewo byłoby modyfikowane?
vzn
@vzn: drzewo B +, drzewo R, drzewo H i drzewo X to tylko niektóre przykłady.
Reza
oczywiście, ale podejrzewam, że do tej pory nikt nie próbował używać drzew wycinanych linkami w indeksach DB. jest to wiarygodna aplikacja, ale nie wydaje się jasne, że są zoptymalizowane pod kątem tych samych operacji, które występują w indeksach DB.
vzn
5

ten dokument stwierdza na końcu, że drzewo z wycięciem łącza (LC) przewyższa drzewa rake-kompresji (RC) dla algorytmu maksymalnego przepływu Sleator / Tarjan przy użyciu standardowego generatora grafów losowych Dimacs.

artykuł koncentruje się na propagacji zmian jako jednej aplikacji dynamicznych drzew. np. propagacja zmian jest podobna do sposobu, w jaki komórki arkusza kalkulacyjnego programu Excel muszą być ponownie obliczane na podstawie zmian w niektórych komórkach na podstawie zależności między komórkami / formułami. autorzy opublikowali swój kod jako otwartą bibliotekę.

Eksperymentalna analiza propagacji zmian w dynamicznych drzewach Acar, Blelloch, Vittes

Propagacja zmian to technika automatycznego dostosowywania wyniku algorytmu do zmian na wejściu. Ideą propagacji zmian jest śledzenie zależności między wywołaniami danych i funkcji, aby w przypadku zmiany danych wejściowych funkcje, których dotyczy zmiana, mogły zostać ponownie uruchomione w celu zaktualizowania obliczeń i danych wyjściowych. Propagacja zmian umożliwia kompilatorowi dynamizowanie algorytmów statycznych.

vzn
źródło
Dziękuję Ci. Miło jest zobaczyć niektóre testy porównawcze algorytmów z udziałem dynamicznych drzew.
Rob Lachlan