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


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