Directed Acyclic Graphs

Abstract

This source code implements a unified framework for pre-processing Directed Acyclic Graphs (DAGs) to lookup reachability between two vertices as well as compute the least upper bound of two vertices in constant time. Our framework builds on the adaptive pre-processing algorithm for constant time reachability lookups and extends this to compute the least upper bound of a vertex-pair in constant time.

The theoretical details of this work can be found in the research paper which is available at http://uhra.herts.ac.uk/handle/2299/12152