Highly Parallel Dynamic Data Structures for Graphs
Dr. William Hesse
Clarkson University
November 6, 2003
12:40 - 1:40pm
Bailey Hall 312

We will present new dynamic data structures for keeping track of a deterministic graph, which is a directed graph of outdegree one. We will allow edges of this graph to change, and we must keep track of the paths through the graph. We need to answer the question "does the path starting at vertex v reach vertex u?" without following all the edges between v and u.

This problem, also known as path following, pointer chasing, or deterministic transitive closure, is like going on a treasure hunt, where each clue tells you the location of the next clue. Meanwhile, someone keeps changing the clues.

We present a dynamic data structure that keeps track of the deterministic graph and can process path queries and edge updates in constant time on a parallel random access machine (PRAM). This data structure contains only O(n log n) bits and uses only O(n) processors for a deterministic graph with n vertices. We will also present versions of this data structure which are larger, but can be computed in constant time on more restricted versions of the PRAM. Finally, we describe the dynamic complexity classes these algorithms fall into.

Lunch will be provided at 12:00 in Steinmetz 237, and a question session for students will follow the talk, also in Steinmetz 237.