|
Die Arbeit von Baruch Schieber und
Uzi Vishkin zum Thema ON FINDING LOWEST COMMON ANCESTORS:
SIMPLIFICATION AND PARALLELIZATION behandelt folgendes Problem:
Gegeben sei ein Baum T(V,E), mit dem man eine
Vorverarbeitung durchführen kann. Bestimme den kleinsten gemeinsamen
Vorverarbeitung durchführen kann. Bestimme den kleinsten gemeinsamen
Vorfahren (Lowest Common Ancestor) von zwei Knoten x,y
in T. Die
Autoren stellen einen Algorithmus vor, der nach linearer Vorverarbeitung solche
LCA-Anfragen in konstanter Zeit beantwortet. Eine Parallelisierung der
Vorverarbeitung unter Verwendung einer optimalen Zahl von Prozessoren auf einer
EREW PRAM liefert sogar logarithmische Laufzeit für die Vorarbeit.
EREW PRAM liefert sogar logarithmische Laufzeit für die Vorarbeit.
Literatur
- B. Schieber und U. Vishkin:
On finding lowest common ancestors: Simplification and parallelization.
SIAM Journal on Computing 17:1253-1262, 1988.
|