Diese Arbeit beschreibt den Algorithmus von Bender und Farach-Colton zur Lösung des Problems des letzten gemeinsamen Vorfahren (engl.: Least Common Ancestor). Bei diesem algorithmischen Problem soll ein gegebener Baum möglichst effizient vorverarbeitet werden, so dass anschließend Anfragen bezüglich des letzten gemeinsamen Vorfahren für beliebige Knotenpaare in konstanter Zeit beantwortet werden können. Die Hauptidee des Algorithmus ist die Reduktion auf das Range Minimum Query-Problem. Diese Arbeit beschreibt detailliert die Herleitung einer solchen Vorverarbeitung und illustriert den Nutzen des entwickelten Algorithmus anhand ausgewählter Beispiele. Anschließend wird die Verallgemeinerung des Problems auf gerichtete azyklische Graphen skizziert.

This paper provides an extended overview on the solution to the problem of the least common ancestor algorithm, based on the findings of Bender and Farach-Coltonin 2000. The content of this algorithmic problem is to efficiently preprocess any given tree in such a way that queries to the least common ancestor of any pair of nodes can be answered in constant time. The main idea of the presented algorithm mostly consists of a reduction to the range minimumq uery-problem. This paper elaborates the derivation of the preprocessing and illustrates the benefits of the developed algorithm through well-chosen examples. Finally, we sketch the least common ancestor problem for general directed acyclic graphs.

1. Einleitung
2. Grundlegende Begriffe und Definitionen
   1. Das Least Common Ancestor-Problem (LCA)
   2. Das Range Minimum Query-Problem (RMQ-Problem)
   3. Euler-Tour und Level-Array
   4. Reduktion von LCA auf RMQ
3. Lösungsansätze für das RMQ-Problem
   1. Die naive Lösung von RMQ
   2. Ein schnellerer RMQ-Algorithmus mittels „sparse dynamic programming“
4. Ein (O(n),O(1))-Algorithmus für das ±1 RMQ-Problem
   1. Vorbetrachtung
   2. Der algorithmus
      1. Überblick
      2. Auswahl der Subarrays
      3. Beantwortung von RMQ-Anfragen
      4. In-Block-Anfragen
      5. Laufzeitanalyse
   3. Zusammenfassung
5. Ein schneller RMQ-Algorithmus
   1. Der kartesische Baum
   2. Der Algorithmus
      1. Vorverarbeitung
   3. Amortisierte Laufzeitanalyse
   4. Korrektheit und Laufzeit des RMQ-Algorithmus
6. Zwei Anwendungsbeispiele und eine Verallgemeinerung
   1. Maximale Palindrome
      1. Das LCE-Problem
      2. Ermittlung maximaler Palindrome
   2. Längste gemeinsame Teilstrings von mehr als zwei Strings
      1. Grundlegendes
      2. Der Algorithmus
      3. Laufzeitanalyse
   3. Das LCA-Problem in gerichteten azyklischen Graphen
      1. Definition letzter gemeinsamer Vorfahre in DAGs
      2. Die Suche nach letzen gemeinsamen Vorfahren in DAGs
      3. Ahnentafeln, Ahnenforschung und Erbkrankheiten

• [AGM91] Noga Alon and Zvi Galil and Oded Margalit. On the exponent of the all pairs shortest path problem. Proceedings of the 32nd annual symposium on Foundations of computer science, pages 569-575, Oktober 1991.
• [AHU73] Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman. On finding lowest common ancestors in trees. Proc. 5th ACM Symp. Theory of Computing (STOC), pages 253-265, 1973.
• [AKGR02] Stephan Alstrup and Haim Kaplan and Cyril Gavoille and Theis Rauhe. Nearest Common Ancestor: A Survey and a new Distributed Algorithm, pages 258-264, 2002.
• [BFC00] Michael A. Bender and Martin Farach-Colton. The LCA Problem Revisited, Lecture Notes In Computer Science; Vol. 1776, pages 88-94, 2000.
• [BPSS01] Michael A. Bender and Giridhar Pemmasani and Steven Skiena and Pavel Sumazin. Finding Least Common Ancestors in Directed Acyclic Graphs, Proceedings of the twelfth annual ACM-SIAM Symposium on Discrete algorithms, pages 845-854, 2001.
• [BV93] Omer Berkman and Usi Vishkin. Recursive Star-Tree Parallel Data Structure, SIAM Journal on Computing 22, pages 221-242, 1993.
• [CLRS01] Thomas H. Cormen and Charles E. Leiserson and Ronald Rivest and Cliffort Stein. Algorithmen - eine Einführung, Oldenburg, 2001.
• [CW87] Don Copperssmith and Samuel Winograd. Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth Annual ACM Symposium on Theory of Computing, pages 1-6. 1987
• [Fre76] Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM journal Compute 5, pages 83-89, März 1976.
• [GT83] Harald N. Gabow and Robert Endre Tarjan. A Linear-Time Algorithm for a special case of disjoint set union, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pages 246-251, 1983.
• [Gus97] Dan Gusfield. Algorithms on Strings, Trees, and Sequences, Cambridge University Press. 1997
• [Heu08] Volker Heun. Skriptum zur Vorlesung Algorithmen und Sequenzen, Ludwig-Maximilian-Universität München, am Lehrstuhl fuer Praktische Informatik und Bioinformatik, 2008.
• [JIS93] R.W. Cottingham Jr. and R.M. Indury and A.A. Schäffer. Genetic linkage computations, American Journal of Human Genetics, 53, pages 252-263, 1993.
• [Sei92] Raimund Seidel. On the all-pairs-shortest-path problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 745-749, 1992.
• [Tar79] Robert Endre Tarjan. Applications of path compression on balanced trees, Journal of the ACM 26, pages 690-715, 1979.
• [wiki10] http://en.wikipedia.org/wiki/Lowest_common_ancestor, 28.04.2010.
• [Zwi98] Uri Zwick. All pairs shortest paths in weighted directed graphs - exact an almost exact algorithms, Annual Symposium on Foundations of Computer Science, pages 310-319, Okt. 1998.