Fast Parallel Algorithms for the Transitive Closure and the Context-Free-Language (CFL) Reachability Problem
Project
Fast Parallel Algorithms for the Transitive Closure and the Context-Free-Language (CFL) Reachability Problem
Principal Investigator
Oracle Principal Investigator
Cristina Cifuentes, Vice President, Software Assurance
Summary
Our aim is to find efficient algorithms to compute the transitive closure of directed graphs, and then to generalise this to compute CFL-reachability. In our research, we will explore the problem space consisting of low complexity algorithms, highly efficient data structures, and suitable implementations that utilise modern parallel hardware architectures. There is a large body of research in this area, with many new papers published in the last five years. The aim of this project is to systematically evaluate this research, improve it where appropriate, and find the best algorithms and data structures suitable for the type of graph that is investigated in the points-to analysis of Java programs. Criteria that define the fitness of the evaluated algorithms and data structures are construction time, memory requirements, and query time.