najlepiej znany algorytm przechwytywania dla wykresu

Question

Co jest najbardziej znanym algorytmem przechwytywania dla grafów skierowanych?

Obecnie używam algorytmu Warshall, ale jego O (n^3). Chociaż z powodu reprezentacji wykresu moja implementacja jest nieco lepsza (zamiast sprawdzać wszystkie krawędzie, sprawdza tylko wszystkie wychodzące krawędzie). Czy istnieje jakiś algorytm zamknięcia przechodniego, który jest lepszy od tego? W szczególności, czy istnieje coś specjalnie dla wielowątkowych architektur pamięci współdzielonej?

Z góry dziękuję.

Raghava.

Answer 1

Na Algorithm Design manual można znaleźć przydatne informacje. Kluczowe punkty:

• Zamknięcie przejściowe jest tak trudne jak mnożenie macierzy; więc najlepiej znaną granicą jest Coppersmith–Winograd algorithm, która działa w O (n^2,376), ale w praktyce prawdopodobnie nie warto używać algorytmów mnożenia macierzy.
• Aby przyspieszyć heurystycznie, oblicz najpierw silnie połączone komponenty.

Answer 2

Dokument ten opisuje działanie różnych algorytmów przechodniego Zamknięcie:

http://www.vldb.org/conf/1988/P382.PDF

Interesujący pomysł z papieru jest wyeliminowane ponowne obliczenie całą Zamknięcie zmian wykresu.

Jest też ta strona Esko Nuutila, który wymienia kilka nowszych algorytmów:

http://www.cs.hut.fi/~enu/tc.html

Jego praca doktorska wymieniony na tej stronie może być najlepszym miejscem do rozpoczęcia:

http://www.cs.hut.fi/~enu/thesis.html

Od tej stronie:

Eksperymenty wskazują również, że z reprezentacją przedziału i nowymi algorytmami, zamknięcie przechodnie można obliczyć w postaci liniowej w stosunku do wielkości wykresu wejściowego.