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/