Werden Link-Cut-Bäume jemals in der Praxis verwendet, für die Berechnung des maximalen Durchflusses oder für andere Anwendungen?

20

Bei vielen Max-Flow-Algorithmen, die meiner Meinung nach implementiert sind, bei Dinics Algorithmus, Push Relabel und anderen, können die asymptotischen Zeitkosten durch die Verwendung dynamischer Bäume (auch als Link-Cut-Bäume bezeichnet) verbessert werden .

Push-Relabel läuft in oder oder $O(V^2E)$ $O(V^3)$ normal, aber mit dynamischem Bäumen $O(V^2\sqrt{E})$ $O(VE \log(V^2/E))$
Dinics Algorithmus läuft in , aber mit dynamischen Bäumen $O(V^2E)$ $O(VE\log(V))$

Praktische Implementierungen von Max-Flow-Algorithmen in den meisten Bibliotheken scheinen diese Datenstruktur jedoch nicht zu nutzen. Werden in der Praxis jemals dynamische Bäume für die Berechnung des maximalen Durchflusses verwendet? Oder tragen sie zu viel Overhead, um für reale Problemgrößen nützlich zu sein?

Gibt es andere Problemdomänen, in denen Link-Cut-Bäume verwendet werden?

Diese Frage steht im Zusammenhang mit einer Frage, die ich in der Theorie gestellt habe: Sind einige der modernsten Maximum-Flow-Algorithmen praktisch?

reference-request graphs data-structures network-flow Rob Lachlan
quelle

übersicht / abstieg von link cut trees aber nur states "ist nützlich für anwendungen wie network flow"

vzn

Aus der von Reza zitierten Tarjan-Umfrage geht hervor, dass die linearen Zeitalgorithmen für eine mäßige Anzahl von Eckpunkten / Kanten sehr gut / am besten abschneiden. Dann gibt es einen Schwellenwert für größere Eckpunkte / Kanten, bei denen die logarithmischen Algorithmen den linearen Algorithmus übertreffen. Daher sind die logarithmischen Zugriffs-FNS nützlich und können für sehr große Diagramme erheblich besser sein.

vzn

7

Es gibt einen Artikel mit dem Titel " Dynamische Bäume in der Praxis ", in dem die praktische Umsetzung besprochen wird.

Die anderen Kategorien, mit denen der Link-Cut-Baum effizient verwendet werden kann, befinden sich in der Datenbankindizierung . Sie finden dies im Buch " Database Index Techniques ".

Reza
quelle

Ich denke, das bedarf einiger Ausarbeitung. Bäume sind im Allgemeinen natürlich für Indizes nützlich, aber unter welchen Bedingungen würde der Baum geändert werden?

VZN

@vzn: B + -Baum, R-Baum, H-Baum und X-Baum sind einige Beispiele.

Reza

Natürlich, aber vermutlich hat bis jetzt noch niemand versucht, Link-Cut-Bäume in DB-Indizes zu verwenden. Es ist eine plausible App, aber es scheint nicht klar zu sein, dass sie für dieselben Vorgänge optimiert sind, die in DB-Indizes vorkommen.

vzn

5

Diese Arbeit stellt am Ende fest, dass ein Link-Cut-Baum (LC-Baum) Rake-Compress-Bäumen (RC-Bäumen) für den Sleator / Tarjan-Max-Flow-Algorithmus unter Verwendung eines Standard-Dimacs-Zufallsgraphengenerators überlegen ist.

Das Papier konzentriert sich auf die Ausbreitung von Veränderungen als eine Anwendung dynamischer Bäume. Die Weitergabe von Änderungen ähnelt beispielsweise der Art und Weise, wie Excel-Tabellenzellen bei Änderungen an einigen Zellen basierend auf Zellen- / Formelabhängigkeiten neu berechnet werden müssen. Die Autoren haben ihren Code als offene Bibliothek veröffentlicht.

Eine experimentelle Analyse der Veränderungsausbreitung in dynamischen Bäumen Acar, Blelloch, Vittes

Die Änderungsweitergabe ist eine Technik zum automatischen Anpassen der Ausgabe eines Algorithmus an Änderungen in der Eingabe. Die Idee hinter der Weitergabe von Änderungen besteht darin, die Abhängigkeiten zwischen Daten- und Funktionsaufrufen zu verfolgen, sodass bei Änderungen der Eingabe die von dieser Änderung betroffenen Funktionen erneut ausgeführt werden können, um die Berechnung und die Ausgabe zu aktualisieren. Die Weitergabe von Änderungen ermöglicht es einem Compiler, statische Algorithmen zu dynamisieren.

vzn
quelle

Vielen Dank. Es ist schön, einige Benchmarks von Algorithmen mit dynamischen Bäumen zu sehen.

Rob Lachlan

Werden Link-Cut-Bäume jemals in der Praxis verwendet, für die Berechnung des maximalen Durchflusses oder für andere Anwendungen?

Antworten: