Answering Reachability Queries on Directed Graphs
Mengmeng Liu, University of Pennsylvania

There are numerous applications that need to query reachability
between nodes in the graph, such as XML databases, social networks,
bioinformatics, etc. Reachability query has attracted a lot of
research attention in many years as it is not only common on graph
databases but also serves as fundamental operations for many other
graph queries. Thus, how to efficiently answer reachable queries
becomes an important issue.

The following paper from SIGMOD'08 has touched this old problem. It is
essentially an algorithmic paper and contains a concise survey on
traditional methods as well. I will briefly talk about this paper as
well as some background on this topic before we have some discussions.
Hopefully this talk can bring up some connections to topics we are
already familiar with.

"Efficiently answering reachability queries on very large directed
graphs": http://portal.acm.org/citation.cfm?doid=1376616.1376677