### DIMACS Theoretical Computer Science Seminar

Title: Streaming Algorithms for Graph Problems

Speaker: **Sampath Kannan**

Date: May 3, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:
We consider algorithms for various common graph problems in
the streaming model. For graphs with n vertices and m edges, we conclude
that o(n) space is insufficient for any interesting problem. We then
focus on what can be computed in space n polylog n with one or more
passes. We show approximation an approximation algorithm for problems
such as matching, diameter, distances between queried pairs of vertices,
etc. and prove matching lower bounds in some cases.

Joint work with Andrew McGregor, Sid Suri, Jian Zhang, and Joan Feigenbaum

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html