Abstract
We present a space efficient method for computing ancestor information in trees, specifically, whether one node is an ancestor of another and the lowest common ancestor of two nodes. We show the method is tunable to specific applications, and compare it to other methods. Finally, we apply our procedures to the problem of finding negative cycles in sparse graphs.

This publication has 11 references indexed in Scilit: