Processing graph streams: Upper and lower bounds, June 2009. Talk at Workshop on Algorithms and Models for Complex Networks, Bristol UK.

In the graph streaming model of computation, we see the input graph presented as a sequence of edges, in some arbitrary order, and must perform computations with one or few passes over this input. Crucial parameters are the amount of working memory needed, and the time per update.

In this talk, I'll discuss some of the key results in this youthful field. These include:

• lower bounds on the memory needed for fundamental computations (testing connectedness and bipartiteness)
• very small memory algorithms for approximating properties of the degree sequence and counting small subgraphs
• constructing spanners and matchings with memory proportional to the number of nodes but sublinear in the number of edges
• extensions to cases where each edge may be duplicated multiple times

[ bib | slides ] Back

This file was generated by bibtex2html 1.92.