Skip to main content

CSE Doctoral Student Seminar: Yifan Xu

Oct 5, 2018
12:30 p.m.
2 p.m.
Lopata Hall, Room 101

‚Äč"Reachability in Nearly Series-Parallel DAGs"

Yifan Xu
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.