Oct 5, 2018
Lopata Hall, Room 101
"Reachability in Nearly Series-Parallel DAGs"
Adviser: Angelina Lee
Reachability is an important research topic in applications such as race detection. In my talk, I will present a parallel algorithm for answering reachability query in nearly series-parallel (SP) directed acyclic graphs (DAGs). The algorithm contains two parts: (1) a construction algorithm to construct data structure which is necessary for answering queries and (2) a query algorithm for answering reachability queries. Given as input a graph comprising an n-node series-parallel graph and k additional non-SP edges, the total construction time of the data structure is O(n+k^2), and each reachability query can be answered in O(lg k) time.