Die vorliegende Bachelorarbeit gibt einen Überblick über den aktuellen Forschungsstand zur Lösung des Lowest Common Ancestor (LCA) in Bäumen. Im Folgenden werden die wichtigsten Ansätze und Techniken systematisch vorgestellt und bewertet.

Zunächst wird das Konzept des LCA definiert: Der LCA zwischen zwei gegebenen Knoten u und v in einem Baum T ist der letzte gemeinsame Vorfahre, der beide Knoten auf seinem Pfad verbindet. Dieses Problem wurde erstmals 1973 von Alfred Aho, John Hopcroft und Jeffrey Ullman in Finding the Least Common Ancestor in Trees beschrieben und stellt eine grundlegende Frage der Graphentheorie dar. Anschließend werden verschiedene Lösungsansätze und Techniken, insbesondere die von Harel & Tarjan, Schieber & Vishkin sowie Bender & Farach-Colton, vorgestellt, analysiert und miteinander verglichen.