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:

bib | slides ] Back

This file was generated by bibtex2html 1.92.