Zur Suche nach dem niedrigsten gemeinsamen Vorfahren: Vereinfachung und Parallelisierung

Wir betrachten folgendes Problem. Angenommen, ein verwurzelter Baum T steht für die Vorverarbeitung zur Verfügung. Beantworten Sie Online-Abfragen, die den niedrigsten gemeinsamen Vorfahren für jedes Paar von Knoten in T anfordern. Wir präsentieren einen Algorithmus zur linearen Zeit- und Raumvorverarbeitung, der es uns ermöglicht, jede Anfrage in O (1) Zeit zu beantworten, wie in Harel und Tarjan SIAM J. Comput., 13 (1984), S. 338–355. Unser Algorithmus hat den Vorteil, einfach und leicht parallelisierbar zu sein. Der resultierende parallele Vorverarbeitungsalgorithmus läuft in logarithmischer Zeit unter Verwendung einer optimalen Anzahl von Prozessoren auf einem EREW PRAM. Jede Anfrage wird dann in O (1) Zeit mithilfe eines einzelnen Prozessors beantwortet.