bekanntester transitiver Abschlussalgorithmus für Graph

Question

Was ist in Bezug auf die Laufzeit der bekannteste transitive Abschlussalgorithmus für gerichtete Graphen?

Ich benutze derzeit den Warshall-Algorithmus, aber seinen O (n^3). Obwohl meine Implementierung aufgrund der Graphendarstellung etwas besser ist (anstatt alle Kanten zu überprüfen, werden nur alle ausgehenden Kanten überprüft). Gibt es einen transitiven Schließalgorithmus, der besser ist? Gibt es speziell etwas für Multi-Thread-Architekturen mit gemeinsam genutztem Speicher?

Vielen Dank im Voraus.

Raghava.

Answer 1

Die Algorithm Design manual hat einige nützliche Informationen. Schlüsselpunkte:

• Transitiver Verschluss ist so schwierig wie Matrixmultiplikation; so ist die bekannteste Grenze die Coppersmith–Winograd algorithm, die in O läuft (n^2.376), aber in der Praxis lohnt es sich wahrscheinlich nicht, Matrixmultiplikationsalgorithmen zu verwenden.
• Berechnen Sie für eine heuristische Beschleunigung zuerst stark verbundene Komponenten.

Answer 2

Dieser Beitrag diskutiert die Leistung verschiedener transitive Erweiterung Algorithmen:

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

Eine interessante Idee aus dem Papier ist recomputing den gesamten Verschluss wie die Grafik, die Änderungen zu vermeiden.

Es gibt auch diese Seite von Esko Nuutila, die ein paar neueren Algorithmen aufgeführt:

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

Seine Doktorarbeit auf dieser Seite aufgeführten kann der beste Ort, um zu starten:

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

Von dieser Seite:

Die Experimente zeigen auch, dass mit der Intervalldarstellung und den neuen Algorithmen der transitive Verschluss typischerweise linear zur Größe des Eingabegraphen berechnet werden kann.