IBM Israel Research Seminars

Rooted trees are omnipresent in Computer Science 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 LA 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.

About the Speaker
Amir ben-Amram Studied Computer Science at Tel-Aviv University, worked for a short while as a student in HRL, and is now a professor at Tel-Aviv Academic College.