Date: 29 Aug 2007 From: jyrki@diku.dk Subject: Guest talk Title: The Euler Path to Level-Ancestor Queries Speaker: Amir ben-Amram (A long-term visitor at DIKU) Time: Wednesday, 5 September 2007, 10.15–11.00 (with a possible extension to 12.00) Place: N034 at DIKU Abstract: Rooted trees are omnipresent in computing and efficient data structures for navigation in large tree structures are desirable for a host of applications. A level-ancestor query on a rooted tree is: Given a vertex v and an integer i > 0, find the i'th vertex on the path from the root to v. There are several published algorithms that preprocess a tree in O(n) (linear) time and space for constant-time level-ancestor queries. However one of the simplest and most efficient methods, using the Euler Path representation of a tree as proposed by Berkman and Vishkin (1990,1994), has been mostly ignored or considered (wrongly) to be impractical. My purpose in this talk is to present this method and argue that it does yield a simple and efficient solution. Amir ben-Amram's home page: http://www2.mta.ac.il/~amirben/ PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/