Ferienakademie 1999
Kurs 2: Bäume - Algorithmik und Kombinatorik

Klaus Holzapfel
Dynamic-Trees und Anwendungen in Flußalgorithmen

Dieser Seminarvortrag stellt die Datenstruktur der Dynamic Trees, ein sich dynamisch ändernder Wald von Bäumen, vor. Es werden verschiedene Möglichkeiten zur Wald von Bäumen, vor. Es werden verschiedene Möglichkeiten zur Implementierung erläutert, wobei jeweils die Komplexität und Einfachheit besprochen wird. Diese Implementierungen stützen sich auf die Implementierungen stützen sich auf die Datentypen Biased Binary Trees bzw. Splay Trees. Beide Implementierungen haben gemeinsam, daß ein Dynamic Tree durch eine Sammlung von knotendisjunkten Pfaden dargestellt wird.

Abschließend wird die Anwendung der Dynamic Trees in einer Variante des Push-Relabel-Algorithmus zur Bestimmung des maximalen Flusses in einem Graphen erläutert.

Literatur
  • Andrew V. Goldberg und Robert E. Tarjan: A new approach to the maximum-flow problem. J. ACM 35(4):921--940, 1988.
  • D.D. Sleator und R.E. Tarjan: A data structure for dynamic trees J. Comput. Syst. Sci. 26(3):362--391, 1983.
  • D.D. Sleator und R.E. Tarjan: Self-adjusting binary search trees. J. ACM 32(3):652--686, 1985.