Abstract:
Fast distance querying in certain types of graphs is often used in databases, ranked keyword search, XML databases, social networks, games and for other purposes. As graphs within these categories get larger and larger, the need for faster query algorithms increases. But since the same graphs are used for many different queries, it is sometimes best to find a fast way of answering a single query at a time after a fairly quick preprocessing stage. I will be looking at both the directed and undirected case for a specific kind of graph, trying to look at ways of speeding up queries as much as possible. Series parallel graphs are not only widely used, but are an essential step into solving general distance queries. They are the 2nd simplest kind of graphs (after trees), and thus are essential to our understanding of how computation works.
Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc/4.0/